Longest Common Subsequence (LCS) extension for vectors.
Project description
LCSvec
Longest Common Subsequence/Substring (LCS) solving package for vectors.
Why LCSvec
While looking for fast implementations solving the Longest Common Subsequence and Longest Common Substring (i.e. Contiguous Subsequence) (LCCS) problems, I only found pieces of code for strings, while I needed something working for vectors of integers. Yet, string LCS implementations 1) work at the character level, which might not be suitable for certain use-cases where one wants to work at word or sentence level; 2) only work with strings, other modalities will not work and might not be designed to be converted to bytes.
LCSvec aims to solve this gap by providing user-friendly and fast implementations of the LCS and LCCS problems for vectors. It works with numpy, pytorch, tensorflow and jax arrays/tensors! The code is written in C++ and the methods are bind with Python with nanobind for optimal performances.
Example
You can install the package with pip: pip install lcsvec
.
Here we will use numpy, the usage for other deep learning libraries is the same.
from lcsvec import lccs, lccs_length, lcs, lcs_length
import numpy as np
seq1 = np.arange(0, 12)
seq2 = np.array([8, 0, 1, 2, 8, 2, 3, 4, 5, 6], dtype=np.int64)
lcs_ = lcs(seq1, seq2) # [0, 1, 2, 3, 4, 5, 6]
lcs_len = lcs_length(seq1, seq2) # 7, more efficient than calling len(lcs(seq1, seq2))
lccs = lccs(seq1, seq2) # [2, 3, 4, 5, 6]
lccs_len = lccs_length(seq1, seq2) # 5, more efficient than calling len(lccs(seq1, seq2))
TODOs
- implement lccs with suffix tree;
- batch methods, i.e. supporting 2D arrays;
- batch methods with any number of dimensions (nD array) and add a
dim
argument; - make it work with an unlimited number of sequences, and set
dim
andpad_token
as kwargs only;
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for lcsvec-0.0.1-pp39-pypy39_pp73-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 34e43668e79fb8c114e98736972cc135c36cd50adbb641bc732717bbeb613985 |
|
MD5 | d2e9c6611d23aee59ee6d892f8419e5f |
|
BLAKE2b-256 | eb8bcb7ffc040bdb242f8c5955238647b90402e2fa632680d489282dfe80328b |
Hashes for lcsvec-0.0.1-pp39-pypy39_pp73-manylinux_2_28_x86_64.manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4ed4c971c2fd31a4d986db7b1c28a95694169e0bc4257067fcae84ff42c0bdd |
|
MD5 | ef12b90a7ab443bc00ae4135a58c1d12 |
|
BLAKE2b-256 | 7b35501977c5bc5b239290c7ae42a1b3d7645b4d4f91251674494f0a3390e35c |
Hashes for lcsvec-0.0.1-pp39-pypy39_pp73-manylinux_2_28_aarch64.manylinux_2_24_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5a01ecfeda958bbb4c8e0e61332a44219cde868b5f1cead3f7410868bf1c90fd |
|
MD5 | 901e11063d8b7030dceef3fd0ed2ae3f |
|
BLAKE2b-256 | 5248a29b00c0d60d4102f6b1483a30586c241ee58a7dcd542f6ea98db1d856d1 |
Hashes for lcsvec-0.0.1-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d1c5f71043ea6720d4099271ae50bb80edabea6cb2d43f210174ec5b01a9233c |
|
MD5 | 2628780e1fdf2769d4904a60dc244797 |
|
BLAKE2b-256 | 2e6e79ec44f94b51ceff00a407b3885118af7fad4cc468a6c1549a94a5e0e992 |
Hashes for lcsvec-0.0.1-cp312-cp312-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8c5a37a887148ca52e74e621e98af5e73d633361ba4de254e10827fdc0a9cfbc |
|
MD5 | 28227ac41f6eb8b84287255546db4077 |
|
BLAKE2b-256 | e1daa35bbc56ddcd89f4a73b1323c6a318a8f034add42e9a8039f09c462a4702 |
Hashes for lcsvec-0.0.1-cp312-cp312-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f4b4bc1269f717b9c291d201e99c47eac609c7630afb46d62e8385d256455e62 |
|
MD5 | 6d401924dce24a2d09ef2fe0b39343b6 |
|
BLAKE2b-256 | c0e8dc634c22d91826df5df4556db6cc5e7ca051e4e92b1821218856194c2cdd |
Hashes for lcsvec-0.0.1-cp312-cp312-musllinux_1_2_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3787292abd6b8a15d4f392d4c30efed11a5e7153c3d983db4a465d5bdf412d02 |
|
MD5 | 2aed0085f45a5920d0ac145b25ee23ce |
|
BLAKE2b-256 | 0ad8bf7f1ea629734eaf0a42082c4a5dcdef2d65888ae909fb898363828f5a19 |
Hashes for lcsvec-0.0.1-cp312-cp312-musllinux_1_2_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 719313373235699ee9b8bbefd7c60b91ffe9530c6ae9c94b90e3de425098ac65 |
|
MD5 | 7081ffc1d8b8d9e4fd69e161e2394e7d |
|
BLAKE2b-256 | 194a8893dabede83bf8384399d3fd71ea38ac5dd3ad3d58c4d1f93a6dd725508 |
Hashes for lcsvec-0.0.1-cp312-cp312-manylinux_2_28_x86_64.manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | edc26b6ff5d0eda48ac7e431fd36fa50ce3dd8310e3861f9b7c12598cbff6e53 |
|
MD5 | 37596162491aad32b486263d895232d3 |
|
BLAKE2b-256 | 3929b1baeede8e6e2c3ab595324b098af01b8f1018684ae4396fe31a34e014e5 |
Hashes for lcsvec-0.0.1-cp312-cp312-manylinux_2_28_aarch64.manylinux_2_24_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 403aa00d333935f5df9867d9f3133d6194bd347bd5a764a8b8525ed28ae5e2f3 |
|
MD5 | f300a802124232a257412dcc39ed2562 |
|
BLAKE2b-256 | 6a6fb1c8e6faeb96251a4e43f6fe9a93893619f14d541333f47b62f608092250 |
Hashes for lcsvec-0.0.1-cp312-cp312-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ae83793d487b8726edac96a1119f19c40837ffcea13ca5b5485271b01871b2f7 |
|
MD5 | 59ea89abc0b3e219f59596b43c1bf727 |
|
BLAKE2b-256 | 1de046d2b1948c5439d6ada049f9d1b1b421759d98a9666b7ca7074894e2152f |
Hashes for lcsvec-0.0.1-cp312-cp312-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3667efad053585ab25ad455590d3fc4a4178c778ad89a58e7fa10a92c44fa660 |
|
MD5 | c5f1f10357927d12eef69caf32fa2467 |
|
BLAKE2b-256 | 2a890c3fccd17d5868d231e2cada2fc1634d78a5e884ed62d7ecf4e37827b89a |
Hashes for lcsvec-0.0.1-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c3b3a12ba2ba59a3d57d6dbff32c9e385a4fbf6a47cc40791bd194abefa74b11 |
|
MD5 | 6c6df0e8363ecb4911152023b6fae037 |
|
BLAKE2b-256 | 7e67a225295c444e5be91362fefbbf73b4550f233db0ab7940c5a78be7eb7b6f |
Hashes for lcsvec-0.0.1-cp311-cp311-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 17a0798ba71df33c9b1497c026effa8a52664fd21584eaf4563eddfa040ecf4c |
|
MD5 | 21a8f9617cfc4745ec6ef60b5182c3e3 |
|
BLAKE2b-256 | 45b97cdb287f4c8b725120fa8e84737c26f0b22e29438d613a8aae27d324b0be |
Hashes for lcsvec-0.0.1-cp311-cp311-musllinux_1_2_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4a6b5c41e259d876f7b3a862d05a20fe35d964550fff5218033a6dd8d33dab20 |
|
MD5 | b7226968f9b91cb1c849a241ed85dcb1 |
|
BLAKE2b-256 | 11c7b7bc6dc6af8d8d207adcd3222a08da49bca4befd98b4f2a9b5778603277d |
Hashes for lcsvec-0.0.1-cp311-cp311-musllinux_1_2_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 62bef2df6d18c95b4ba7ed48d4ea7e9f6c0ddaeef726dbc627314e72968efd77 |
|
MD5 | 4d30ceda88400a2cf6757f0f6ad10fd8 |
|
BLAKE2b-256 | b4db99e9628fdfd8603829b093269a65d0e6303aa37fe2a45350581847911ff4 |
Hashes for lcsvec-0.0.1-cp311-cp311-manylinux_2_28_x86_64.manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0fd9bb620787e6050434ddee6706a301321ca76a15364b99189d41c3ca016daa |
|
MD5 | 8d027bb2deedfa59dd2f77ea834ed4a8 |
|
BLAKE2b-256 | f4659fdea63d40d9d404b9d3d46a03f3e8c32143d8d11ac92950e70c0c78d2b9 |
Hashes for lcsvec-0.0.1-cp311-cp311-manylinux_2_28_aarch64.manylinux_2_24_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 009a824a28cc873ad1f6491fbfeaae3c1afde0cdf89890bcdb97ad8bab7093e0 |
|
MD5 | 102d443f251c6010c3a88f90e8cd310d |
|
BLAKE2b-256 | 4685cb830ff66199fe199d4ba5fc9dd82434175e971251a25e6c6935808e1171 |
Hashes for lcsvec-0.0.1-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7c43c0ce7426ba3c156a8f0c97cc6d4da2fbcd3b7e8a35008dfb6349a388777e |
|
MD5 | ca92e628252ddc4ce088866ab28c9045 |
|
BLAKE2b-256 | aa16a0af5ce3df66a38db24980ba9a60b158a385a0fffd45f1378065186b091e |
Hashes for lcsvec-0.0.1-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 52e49456d95b02cd602ab56a7f79de15acedf0f7afa1755a9547212a4ce5920f |
|
MD5 | 8bd0c4a0b5b79fec47936bfcf3bf6d44 |
|
BLAKE2b-256 | 7f2a3fee92dc0752751c480f73307bfbe1d7a4723a9dc30f0918b8ed44a0ade3 |
Hashes for lcsvec-0.0.1-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e1af0f8c3f7cd202278f576a11a2076d8e80ea4c1c7c60b1207e0eb10cc744da |
|
MD5 | 123174a51664a3e06f83e1b16de2dbe6 |
|
BLAKE2b-256 | 3a3c7c04a00c2ffc8dfe3b78af489210f523201e02c67bdad04758b4287ac401 |
Hashes for lcsvec-0.0.1-cp310-cp310-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d5781c5e84b820f41a7636144ce633ba3ea88a64c9eac242717ea2c53f0090a6 |
|
MD5 | 63b90aa449281f9bf5f1b5bc857655e0 |
|
BLAKE2b-256 | 968c00c704d6f5f32bb17e1edd0b966de42747d5833e9846c2b837bb7f80a019 |
Hashes for lcsvec-0.0.1-cp310-cp310-musllinux_1_2_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e0d456f9cff481d65c6f3da9bf4dcbc749a4a2bb89e9c4f32742d34a4dd29fd0 |
|
MD5 | 98740ef05402ec4a8e34030ecd100142 |
|
BLAKE2b-256 | 250d67cf0cb79357b6f6ebbf91c704264b8391e521b117c39d2a124523afb4f9 |
Hashes for lcsvec-0.0.1-cp310-cp310-musllinux_1_2_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b0136dea3008b0c8ecb76e9c647a26e44c9578b1ff8cf51b51b5cbb1b7a7f5fd |
|
MD5 | 6b5659c909be9bd2c8e9bbc5acc3e439 |
|
BLAKE2b-256 | 42a7d7c1e80cc15a83d508fd1590127509211f4aa35c949af89f7866662daefd |
Hashes for lcsvec-0.0.1-cp310-cp310-manylinux_2_28_x86_64.manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 29116da80375d84e6c0b429d4457a07acc725efd9c3855b2113687e7763b60c7 |
|
MD5 | eedb8e2c11ecade7ca9f554ba72912d2 |
|
BLAKE2b-256 | 183a90fd0a37c4e357ae3bf7ec560fe0b15fb378b643b8e38e30fb04044fa7ea |
Hashes for lcsvec-0.0.1-cp310-cp310-manylinux_2_28_aarch64.manylinux_2_24_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c67e07c06097d13b374134573b01ff5b8b28db627b0a099d7de400e01c267f1a |
|
MD5 | 6c67139171d6f87268796f9d7fbdb285 |
|
BLAKE2b-256 | fdc335a5fb3fef827b43acbd9351ae4c23a613619fd88673b286c0d20a5dd60d |
Hashes for lcsvec-0.0.1-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b14159a7fbc6b6ff512ecc7d370c3daac044ef5a514bbf49d0827f8b7d6d0edc |
|
MD5 | f483e2b9bc7514b0a222c8f324f4abec |
|
BLAKE2b-256 | 8d8e3c1992048212474e6aa22ed9c8f2461365a9fb5b9bb2e79ea44545013f88 |
Hashes for lcsvec-0.0.1-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c9c1f365164411577cbbb2fcda947682416b68b68530db343c96be971fc41fb7 |
|
MD5 | 9b81168a4894329940c44061be8ecca0 |
|
BLAKE2b-256 | b420b130ba720c181093762221e1351e6e000605d2d17d9864a23f6cbf3b2fa7 |
Hashes for lcsvec-0.0.1-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5fb4e75af5398da792e18f71894ad8367e092a470b8dd2ddab2944e5a6e49021 |
|
MD5 | b4e87de88cd64540e738f29639b84772 |
|
BLAKE2b-256 | b5460ad2092e8f5d3eea45d5f87c076646efc7d6796f72a2d3fe4c4eeb59b4ff |
Hashes for lcsvec-0.0.1-cp39-cp39-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fb89176c0d81d7b80b9a516958d1585c134de273267d406710039d0ade214bd0 |
|
MD5 | ba544ef3cba2861b6bf4d638716370b9 |
|
BLAKE2b-256 | 5f60f644c7814d43daa4df1568ddf8b06d50d3580ae82e1021e0010505000b72 |
Hashes for lcsvec-0.0.1-cp39-cp39-musllinux_1_2_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1ec2a7f5d9dfcab2be0c0303cf45e5901a4243ff9d0d7dbcd983cb20b2948558 |
|
MD5 | 6a742450fc513c48170bfb6b27b5239a |
|
BLAKE2b-256 | b944ab93da7b671d8c4c884d9552ceea447058c22c8254f5f0e8f03602193c72 |
Hashes for lcsvec-0.0.1-cp39-cp39-musllinux_1_2_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3f16ecafdcb96545351faaa875c1be03ee96f4779179cf1e3ee12243cf8d13e2 |
|
MD5 | c461fcdc6b07ffc4ab0a1e84501705d5 |
|
BLAKE2b-256 | 872ebceecaf42dff8d46e4a4e5afff8e85e160289865b205658a2db877fed8f4 |
Hashes for lcsvec-0.0.1-cp39-cp39-manylinux_2_28_x86_64.manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 15b86993498bddf2c0612afadbb26a9a093f144e10c14c0f757b35ef1913dbd1 |
|
MD5 | aa6d0188ad4371b25045d0cd71c5be56 |
|
BLAKE2b-256 | 492491b6d6828f59043cc8fc7d77c6d664288c643c97a3dd08fe73e81d6fc510 |
Hashes for lcsvec-0.0.1-cp39-cp39-manylinux_2_28_aarch64.manylinux_2_24_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 656c3e1de16a62aae5bfb257f0524765792c37293cacf3499283c913141b7cf5 |
|
MD5 | 6295c8dde4819fa5ad8a41adf4acbd68 |
|
BLAKE2b-256 | 806ecba8783084a1d1775868ddd5cf54dc60db955d49313a68941a7a4d32d723 |
Hashes for lcsvec-0.0.1-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fe12656e52a588456e2dc4d53a0c7de2ee71babc6ae228063a050aaf485cc6cf |
|
MD5 | 7946fe14d3a13f6fe6c6332e4de95f31 |
|
BLAKE2b-256 | 9ecf264ef3eda8d3eab83b3bc66a52315a498d4fcb2d47e572d5ff0d22a61c81 |
Hashes for lcsvec-0.0.1-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 05185bd71f52bc7ebf34627ac9909717f6f355a4d1e14ff6abc51d6b37421120 |
|
MD5 | 6adcd5977079cccb344f0de54c3d40c6 |
|
BLAKE2b-256 | c22076724d02223925fb1ffe3ab9f9ded27866e87b84890779ebd1d1c426e449 |
Hashes for lcsvec-0.0.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7600c3bbe7ec378aa7af2d28ed72cafac5d99e0ab91ee39949b33ad9140ee41d |
|
MD5 | eeba2315098f2842130c9326a78efbcc |
|
BLAKE2b-256 | 064116c58c6365470e8d36706d421fb87d8f755df13279c4fe61db887ddffdcb |
Hashes for lcsvec-0.0.1-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2eebdfc7284f3c5e61453c3c246899c37c5245fc9eff7a634d4d71612ceb526d |
|
MD5 | 1e869d623cc798746eb190d3c90e8c53 |
|
BLAKE2b-256 | 97e63e0c77df6576602958cac7dcdb1594af4c4b2f749dcfa3491fa0791ec0ff |
Hashes for lcsvec-0.0.1-cp38-cp38-musllinux_1_2_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5203f01d4a4b67cb0cdf26b5625d1ffb426fdb699660233e470f0ccf57cab549 |
|
MD5 | 96a00ad085668b4269ec34e1d0ac9b01 |
|
BLAKE2b-256 | 8a9e38ca48a7c975e570661abb4b02396623d5e151014600a632990eab6c0c54 |
Hashes for lcsvec-0.0.1-cp38-cp38-musllinux_1_2_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b4f128478a0f16d061f5e9654da595a2c0fa4122f83e62ebd990d1b88cf9c411 |
|
MD5 | 69a046cb61fc7e3abc74a715bba407c4 |
|
BLAKE2b-256 | 7023fb53ca3f35190bbc6198b2dd46d9d22b968e7e89994342f3291111e2463a |
Hashes for lcsvec-0.0.1-cp38-cp38-manylinux_2_28_x86_64.manylinux_2_24_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 34b0d3c62a55535a85a1547f6528188ae3676c081b972d70d8e4f1d5b54cac79 |
|
MD5 | a2c4d3253bb97ac38c23592d601fdb5d |
|
BLAKE2b-256 | 6c338d846386283a351db7d5fba8f18830954db28fbe9d7676349b0ccd9d368e |
Hashes for lcsvec-0.0.1-cp38-cp38-manylinux_2_28_aarch64.manylinux_2_24_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0fa929f9b4f6a1041927f3bf1d22e530546726ff57ecdb5e279ccc6d0de3a9bf |
|
MD5 | 04cc294e67677a4bbfc24543de08cafd |
|
BLAKE2b-256 | 7977d4902707eb777f55c7871f0e2769ea980ed6be63a129e9d9475ff63652a1 |
Hashes for lcsvec-0.0.1-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 55dc39a2477e2ae8dab7979de5091e13b971a94527bf2500ab6d10e2edfd4af2 |
|
MD5 | 4227b3927ca1808c5b40ba0f2aff871d |
|
BLAKE2b-256 | fd3603adcd9eba9c1c21aa7236620a67102b627fcd9368b706cfa1238925e9c8 |
Hashes for lcsvec-0.0.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fbe7f724b22e5ae95f8998e1bcf1a0947d37ea108b9d205e93b52cb015e3c33e |
|
MD5 | 725ebaf8aa4e12b1f1573039545efffc |
|
BLAKE2b-256 | d933b9f2134c85c5afa8f6a1b4a4d2d285d977829828838fc10c53cdd07ac369 |