{
    "info": {
        "author": "A. Samuel Pottinger",
        "author_email": "",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 4 - Beta",
            "Intended Audience :: Developers",
            "Intended Audience :: Financial and Insurance Industry",
            "Intended Audience :: Healthcare Industry",
            "Intended Audience :: Information Technology",
            "Intended Audience :: Legal Industry",
            "Intended Audience :: Science/Research",
            "Intended Audience :: Telecommunications Industry",
            "License :: OSI Approved :: MIT License",
            "Natural Language :: English",
            "Operating System :: OS Independent",
            "Topic :: Scientific/Engineering :: Artificial Intelligence",
            "Topic :: Scientific/Engineering :: Information Analysis",
            "Topic :: Text Processing"
        ],
        "description": "py_common_subseq\n================\nA re-usable Python micro-library that finds all of the subsequences shared\nbetween two sequences (like strings or lists) in polynomial time.\n\n\nAuthor, License, and Conditions  \n-------------------------------\n(c) A. Samuel Pottinger (http://gleap.org), 2013  \nReleased under the [MIT license](http://opensource.org/licenses/MIT). Don't\nforget to be awesome.\n\n\nInstallation (pip)  \n------------------\npip install py_common_subseq\n\n\nInstallation (manual / single file)\n-----------------------------------\nThis mico-library is a single file and engineers that may prefer to include the\nfile directly instead of using pip can simply copy\npy_common_subseq/py_common_subseq.py into an accessible location. This\nmicro-library does not have any additional dependencies beyond the Python\nstandard library.\n\n\nQuickstart  \n----------\n```\n>>> import py_common_subseq\n>>> test_seq_1 = 'qwer'\n>>> test_seq_2 = 'qewr'\n>>> py_common_subseq.count_common_subsequences(test_seq_1, test_seq_2)\n12\n>>> py_common_subseq.find_common_subsequences(test_seq_1, test_seq_2)\nset(['', 'qer', 'wr', 'qwr', 'er', 'qr', 'e', 'qw', 'q', 'r', 'qe', 'w'])\n>>> py_common_subseq.find_common_subsequences(test_seq_1, test_seq_2, sep=',')\nset(['', ',q,w,r', ',e,r', ',e', ',w,r', ',q,w', ',q,r', ',w', ',r', ',q', ',q,e', ',q,e,r'])\n```\n\n\nFull API  \n--------\n```count_common_subsequences(seq_1, seq_2)```   \nFind the number of common subsequences between two collections.\n\nThis function finds the number of common subsequences between two\ncollections but does not return an actual listing of those subsequences.\nThis is more space efficient O(len(seq_1)) than find_common_subsequences.\n\n - **seq_1:** Any integer indexable collection (list, tuple, etc.). The first collection to find subsequences in.\n - **seq_2:** Any integer indexable collection (list, tuple, etc.). The second collection to find subsequences in.\n - **return:** Integer. The number of common subsequences between seq_1 and seq_2.\n\n\n```find_common_subsequences(seq_1, seq_2)```  \nFind the number of common subsequences between two collections.\n\nThis function finds the common subsequences between two collections and\nreturns an actual listing of those subsequences. This is less space\nefficient (O(len(seq_1)^2)) than count_common_subsequences.\n\n - **seq_1:** Any integer indexable collection (list, tuple, etc.). The first collection to find subsequences in.\n - **seq_2:** Any integer indexable collection (list, tuple, etc.). The second collection to find subsequences in.\n - **sep:** Seperator to put between elements when constructing a subsequence. Keyword argument defaulting to ''.\n - **empty_val:** The value to use to represent the empty set. Keyword argument defaulting to ''.\n - **return:** Python standard lib set. Set of subsequences in common between seq_1 and seq_2.\n\n\nMotivation / Background  \n-----------------------\nWhile the longest common subsequence allows for the comparison of sequences,\nsome problem domains also benefit from the additional information hiding in the\nsecond, third, fourth, etc. largest common subsequences ignored by typical LCS.\nThis micro-library provides an implementation of the dynamic programming\nsolution for finding all common subsequences as presented in All Common\nSubsequences (http://dl.acm.org/citation.cfm?id=1625377 - calACS-DP) by\nHui Wang (http://www.ulster.ac.uk/staff/h.wang.html). This micro-library also\nadds some space efficiency improvements and functionality to list common\nsubsequences (semi-formal proof below).\n\n\nTesting  \n-------\nWithin the py_common_subseq folder, run:\n\npython test_py_common_subseq.py\n\nUnit tests do not have any dependencies beyond the Python standard library.\n\n\nOverview of Space and Time complexity\n-------------------------------------\nThe algorithm runs in `O(|A|x|B|)`` time where `|A|` is the length of the first\nsequence provided and `|B|` is the length of the second sequence. Space\ncomplexity is as follows:\n\ncount_common_subsequences: `2 * min(len(seq_1), len(seq_2)) or O(min(|A|, |B|))`\nfind_common_subsequences: `2 * min(len(seq_1), len(seq_2))^2 or O(min(|A|, |B|))^2`\n\nSee the discussion below for additional detail.\n\n\nOverview of Deviations and Optimizations  \n----------------------------------------\nSimilar to the well-documented space optimization for the dynamic programming\nsolution to the Longest Common Subsequence problem, both\ncount_common_subsequences and find_common_subsequences only maintains the\n\"current\" and \"previous\" rows of the table that Hui Wang's algorithm requires.\nAs proven below, this reduces the space complexity to the following:\n\ncount_common_subsequences: `2 * min(len(seq_1), len(seq_2)) or O(min(|A|, |B|))`\nfind_common_subsequences: `2 * min(len(seq_1), len(seq_2))^2 or O(min(|A|, |B|))^2`\n\n\nAdditionally, unlike Professor Wang's original paper, find_common_subsequences\nmodifies the algorithm's table to contain the set of subsequences achieved at\nthe point of the algorithm's execution as opposed to the cardinality of that\nset.\n\n\nDiscussion / proof of correctness  \n----------------------------------\nSee README.md\n\n\nDiscussion of time complexity  \n-----------------------------\nSee README.md\n\n\nDiscussion of space optimization\n--------------------------------\nSee README.md",
        "description_content_type": "",
        "docs_url": null,
        "download_url": "https://github.com/sampottinger/py_common_subseq/archive/master.zip",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/Samnsparky/py_common_subseq",
        "keywords": "all common subsequences ACS dynamic programming",
        "license": "MIT",
        "maintainer": "",
        "maintainer_email": "",
        "name": "py-common-subseq",
        "package_url": "https://pypi.org/project/py-common-subseq/",
        "platform": "",
        "project_url": "https://pypi.org/project/py-common-subseq/",
        "project_urls": {
            "Download": "https://github.com/sampottinger/py_common_subseq/archive/master.zip",
            "Homepage": "https://github.com/Samnsparky/py_common_subseq"
        },
        "release_url": "https://pypi.org/project/py-common-subseq/0.2/",
        "requires_dist": null,
        "requires_python": "",
        "summary": "Microlibrary finding all common subsequences between two sequences in polynomial time.",
        "version": "0.2"
    },
    "last_serial": 5717860,
    "releases": {
        "0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "67f927940e1c7d851e244bfdc91198ed",
                    "sha256": "a95eb6a5a34d2738383f2960c819f05c998a3852e3919c483abf6aae6a47cf34"
                },
                "downloads": -1,
                "filename": "py_common_subseq-0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "67f927940e1c7d851e244bfdc91198ed",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 4556,
                "upload_time": "2013-09-11T00:02:55",
                "url": "https://files.pythonhosted.org/packages/3d/fd/90df2a84e3ddd6c72288692a75ee56dca10250b69622e334f8c9c1491bee/py_common_subseq-0.1.tar.gz"
            }
        ],
        "0.1.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "654fefe57b31526afcdf3fac04f3c891",
                    "sha256": "fae105f04361ddc8d3c0c41c4a7c55de881a4294df2fb77b9d835733ba3dcbb6"
                },
                "downloads": -1,
                "filename": "py_common_subseq-0.1.1.tar.gz",
                "has_sig": false,
                "md5_digest": "654fefe57b31526afcdf3fac04f3c891",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6798,
                "upload_time": "2013-09-14T19:19:58",
                "url": "https://files.pythonhosted.org/packages/35/da/854d4cb01062bd19330cece2e92d8a9f49bc8273b74e6e9de97f0dfb8acd/py_common_subseq-0.1.1.tar.gz"
            }
        ],
        "0.1.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "02ff9631b3ee72ade1f40cba5646a309",
                    "sha256": "409c33608265fde407cf13142c7f447c751f57dfb7fcfad86d4410a648ec3a49"
                },
                "downloads": -1,
                "filename": "py_common_subseq-0.1.2.tar.gz",
                "has_sig": false,
                "md5_digest": "02ff9631b3ee72ade1f40cba5646a309",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 5250,
                "upload_time": "2013-09-14T19:22:07",
                "url": "https://files.pythonhosted.org/packages/1a/85/dced2a9b099441d8d914c10005f55c3a9f0e0f3a4e688dd446e3fdad7095/py_common_subseq-0.1.2.tar.gz"
            }
        ],
        "0.1.3": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "a15929c390ff14faa848945b3f7b7a17",
                    "sha256": "52917e2c81bbe5032b7d77813770e233a36f5698f2adabcdc0b0aa015a34f776"
                },
                "downloads": -1,
                "filename": "py_common_subseq-0.1.3.tar.gz",
                "has_sig": false,
                "md5_digest": "a15929c390ff14faa848945b3f7b7a17",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 7296,
                "upload_time": "2013-09-14T19:30:10",
                "url": "https://files.pythonhosted.org/packages/d0/54/58422b10f66f2a9b9ed47b8e6cd7155485b4efd98db679ba2a3ec074172f/py_common_subseq-0.1.3.tar.gz"
            }
        ],
        "0.1.3.1": [],
        "0.1.4": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "d782686e9d0f30bd48863908d3cbfc06",
                    "sha256": "77fe3cf689b4a25dd9171e31cebba0c3fda0850e80373890b1ab1f650f01f36a"
                },
                "downloads": -1,
                "filename": "py_common_subseq-0.1.4.tar.gz",
                "has_sig": false,
                "md5_digest": "d782686e9d0f30bd48863908d3cbfc06",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 5243,
                "upload_time": "2013-09-14T19:38:53",
                "url": "https://files.pythonhosted.org/packages/63/c9/df4affa7b27f1f2f421ce68503d7fed351d85cb358a86038891ca214b7e6/py_common_subseq-0.1.4.tar.gz"
            }
        ],
        "0.1.5": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "14192ac7181f7539e5d19ba802c5def8",
                    "sha256": "85d26fdf0818c9022c13b737a2b3d72682a100ad4b5f683f8c65f65678092463"
                },
                "downloads": -1,
                "filename": "py_common_subseq-0.1.5.tar.gz",
                "has_sig": false,
                "md5_digest": "14192ac7181f7539e5d19ba802c5def8",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 4877,
                "upload_time": "2019-08-22T23:22:57",
                "url": "https://files.pythonhosted.org/packages/bb/83/5098cc6f7a1b4c60191ed516ec1ef0e2c5e92eb0b8eb5441cbde8ff21116/py_common_subseq-0.1.5.tar.gz"
            }
        ],
        "0.1.6": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "1f05dffba996a61da937d1c8adb73a4f",
                    "sha256": "2d6220309b12dd3f116e5a348480d8abd4524779d7c7777277fa370cb036d75f"
                },
                "downloads": -1,
                "filename": "py_common_subseq-0.1.6.tar.gz",
                "has_sig": false,
                "md5_digest": "1f05dffba996a61da937d1c8adb73a4f",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 4878,
                "upload_time": "2019-08-22T23:25:54",
                "url": "https://files.pythonhosted.org/packages/56/82/c3a0fcd645519a5169a5a6ab069f4c8ccf0afbe44689bc5706393dc000d8/py_common_subseq-0.1.6.tar.gz"
            }
        ],
        "0.1.7": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "7215d29889874747a23990f6780c0781",
                    "sha256": "2666bb3fc9db3f07b99a58e13c2e35bb908104ce1bec0259630482c51556c316"
                },
                "downloads": -1,
                "filename": "py_common_subseq-0.1.7.tar.gz",
                "has_sig": false,
                "md5_digest": "7215d29889874747a23990f6780c0781",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 7973,
                "upload_time": "2019-08-22T23:33:17",
                "url": "https://files.pythonhosted.org/packages/c2/2d/6e5fb2db938b266248cb1d9740ec2eb9ebe89a0b75f1c5cfd475cdbe229e/py_common_subseq-0.1.7.tar.gz"
            }
        ],
        "0.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "4da2e01a5b89aef05700c16990898cb6",
                    "sha256": "60823615402a83b8616a9b13331fd08dc72f615315ed7d0463f07ff1b9b2b778"
                },
                "downloads": -1,
                "filename": "py_common_subseq-0.2.tar.gz",
                "has_sig": false,
                "md5_digest": "4da2e01a5b89aef05700c16990898cb6",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 7982,
                "upload_time": "2019-08-22T23:37:33",
                "url": "https://files.pythonhosted.org/packages/95/13/da6281591d3333c0ac4c219c2f68ad9ad5ce9620b699eacdc5912eb00386/py_common_subseq-0.2.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "4da2e01a5b89aef05700c16990898cb6",
                "sha256": "60823615402a83b8616a9b13331fd08dc72f615315ed7d0463f07ff1b9b2b778"
            },
            "downloads": -1,
            "filename": "py_common_subseq-0.2.tar.gz",
            "has_sig": false,
            "md5_digest": "4da2e01a5b89aef05700c16990898cb6",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 7982,
            "upload_time": "2019-08-22T23:37:33",
            "url": "https://files.pythonhosted.org/packages/95/13/da6281591d3333c0ac4c219c2f68ad9ad5ce9620b699eacdc5912eb00386/py_common_subseq-0.2.tar.gz"
        }
    ]
}