All Projects → life4 → Textdistance

life4 / Textdistance

Licence: mit
Compute distance between sequences. 30+ algorithms, pure python implementation, common interface, optional external libs usage.

Programming Languages

python
139335 projects - #7 most used programming language
Jupyter Notebook
11667 projects
shell
77523 projects

Projects that are alternatives of or similar to Textdistance

Java String Similarity
Implementation of various string similarity and distance algorithms: Levenshtein, Jaro-winkler, n-Gram, Q-Gram, Jaccard index, Longest Common Subsequence edit distance, cosine similarity ...
Stars: ✭ 2,403 (-6.68%)
Mutual labels:  algorithm, distance, levenshtein-distance, damerau-levenshtein
LinSpell
Fast approximate strings search & spelling correction
Stars: ✭ 52 (-97.98%)
Mutual labels:  levenshtein, levenshtein-distance, damerau-levenshtein
stringdistance
A fuzzy matching string distance library for Scala and Java that includes Levenshtein distance, Jaro distance, Jaro-Winkler distance, Dice coefficient, N-Gram similarity, Cosine similarity, Jaccard similarity, Longest common subsequence, Hamming distance, and more..
Stars: ✭ 60 (-97.67%)
Mutual labels:  levenshtein, levenshtein-distance, hamming-distance
Symspell
SymSpell: 1 million times faster spelling correction & fuzzy search through Symmetric Delete spelling correction algorithm
Stars: ✭ 1,976 (-23.26%)
Mutual labels:  levenshtein, levenshtein-distance, damerau-levenshtein
Mygo
Leetcode、剑指offer(第二版)的Go实现😀 Come join us!🤝❤️👻
Stars: ✭ 109 (-95.77%)
Mutual labels:  algorithm, algorithms
Data Structures And Algorithms
A collection of some implementations of data structures and algorithms.
Stars: ✭ 101 (-96.08%)
Mutual labels:  algorithm, algorithms
Thealgorithms
Algorithms repository.
Stars: ✭ 122 (-95.26%)
Mutual labels:  algorithm, algorithms
Data structure and algorithms library
A collection of classical algorithms and data-structures implementation in C++ for coding interview and competitive programming
Stars: ✭ 133 (-94.83%)
Mutual labels:  algorithm, algorithms
Acm Icpc Algorithms
Algorithms used in Competitive Programming
Stars: ✭ 1,281 (-50.25%)
Mutual labels:  algorithm, algorithms
Hackerrank
📗 Solutions of more than 380 problems of Hackerrank accross several domains.
Stars: ✭ 128 (-95.03%)
Mutual labels:  algorithm, algorithms
Funnyalgorithms
A repository with a bunch of funny algorithms, beginners friendly
Stars: ✭ 161 (-93.75%)
Mutual labels:  algorithm, algorithms
Onp
The implementations of "An O(NP) Sequence Comparison Algorithm"
Stars: ✭ 100 (-96.12%)
Mutual labels:  algorithm, diff
Algorithms
A collection of algorithms and data structures
Stars: ✭ 11,553 (+348.66%)
Mutual labels:  algorithm, algorithms
Robotics Coursework
🤖 Places where you can learn robotics (and stuff like that) online 🤖
Stars: ✭ 1,810 (-29.71%)
Mutual labels:  algorithm, algorithms
Algorithms
Algorithms and data structures implemented in JavaScript with explanations, for further readings
Stars: ✭ 99 (-96.16%)
Mutual labels:  algorithm, algorithms
Leetcode Sol Res
Clean, Understandable Solutions and Resources for LeetCode Online Judge Algorithm Problems.
Stars: ✭ 1,647 (-36.04%)
Mutual labels:  algorithm, algorithms
.codebits
📚 List of resources for Algorithms and Data Structures in Python & other CS topics @2017
Stars: ✭ 144 (-94.41%)
Mutual labels:  algorithm, algorithms
Data Structures
Common data structures and algorithms implemented in JavaScript
Stars: ✭ 139 (-94.6%)
Mutual labels:  algorithm, algorithms
Dwifft
Swift Diff
Stars: ✭ 1,822 (-29.24%)
Mutual labels:  algorithm, diff
Algorithmic Toolbox San Diego
✔ My Solutions of (Algorithmic-Toolbox ) Assignments from Coursera ( University of California San Diego ) With "Go In Depth" Part Which Contains More Details With Each of The Course Topics
Stars: ✭ 78 (-96.97%)
Mutual labels:  algorithm, algorithms

TextDistance

TextDistance logo

Build Status PyPI version Status License

TextDistance -- python library for comparing distance between two or more sequences by many algorithms.

Features:

  • 30+ algorithms
  • Pure python implementation
  • Simple usage
  • More than two sequences comparing
  • Some algorithms have more than one implementation in one class.
  • Optional numpy usage for maximum speed.

Algorithms

Edit based

Algorithm Class Functions
Hamming Hamming hamming
MLIPNS Mlipns mlipns
Levenshtein Levenshtein levenshtein
Damerau-Levenshtein DamerauLevenshtein damerau_levenshtein
Jaro-Winkler JaroWinkler jaro_winkler, jaro
Strcmp95 StrCmp95 strcmp95
Needleman-Wunsch NeedlemanWunsch needleman_wunsch
Gotoh Gotoh gotoh
Smith-Waterman SmithWaterman smith_waterman

Token based

Algorithm Class Functions
Jaccard index Jaccard jaccard
Sørensen–Dice coefficient Sorensen sorensen, sorensen_dice, dice
Tversky index Tversky tversky
Overlap coefficient Overlap overlap
Tanimoto distance Tanimoto tanimoto
Cosine similarity Cosine cosine
Monge-Elkan MongeElkan monge_elkan
Bag distance Bag bag

Sequence based

Algorithm Class Functions
longest common subsequence similarity LCSSeq lcsseq
longest common substring similarity LCSStr lcsstr
Ratcliff-Obershelp similarity RatcliffObershelp ratcliff_obershelp

Compression based

Normalized compression distance with different compression algorithms.

Classic compression algorithms:

Algorithm Class Function
Arithmetic coding ArithNCD arith_ncd
RLE RLENCD rle_ncd
BWT RLE BWTRLENCD bwtrle_ncd

Normal compression algorithms:

Algorithm Class Function
Square Root SqrtNCD sqrt_ncd
Entropy EntropyNCD entropy_ncd

Work in progress algorithms that compare two strings as array of bits:

Algorithm Class Function
BZ2 BZ2NCD bz2_ncd
LZMA LZMANCD lzma_ncd
ZLib ZLIBNCD zlib_ncd

See blog post for more details about NCD.

Phonetic

Algorithm Class Functions
MRA MRA mra
Editex Editex editex

Simple

Algorithm Class Functions
Prefix similarity Prefix prefix
Postfix similarity Postfix postfix
Length distance Length length
Identity similarity Identity identity
Matrix similarity Matrix matrix

Installation

Stable

Only pure python implementation:

pip install textdistance

With extra libraries for maximum speed:

pip install "textdistance[extras]"

With all libraries (required for benchmarking and testing):

pip install "textdistance[benchmark]"

With algorithm specific extras:

pip install "textdistance[Hamming]"

Algorithms with available extras: DamerauLevenshtein, Hamming, Jaro, JaroWinkler, Levenshtein.

Dev

Via pip:

pip install -e git+https://github.com/life4/textdistance.git#egg=textdistance

Or clone repo and install with some extras:

git clone https://github.com/life4/textdistance.git
pip install -e ".[benchmark]"

Usage

All algorithms have 2 interfaces:

  1. Class with algorithm-specific params for customizing.
  2. Class instance with default params for quick and simple usage.

All algorithms have some common methods:

  1. .distance(*sequences) -- calculate distance between sequences.
  2. .similarity(*sequences) -- calculate similarity for sequences.
  3. .maximum(*sequences) -- maximum possible value for distance and similarity. For any sequence: distance + similarity == maximum.
  4. .normalized_distance(*sequences) -- normalized distance between sequences. The return value is a float between 0 and 1, where 0 means equal, and 1 totally different.
  5. .normalized_similarity(*sequences) -- normalized similarity for sequences. The return value is a float between 0 and 1, where 0 means totally different, and 1 equal.

Most common init arguments:

  1. qval -- q-value for split sequences into q-grams. Possible values:
    • 1 (default) -- compare sequences by chars.
    • 2 or more -- transform sequences to q-grams.
    • None -- split sequences by words.
  2. as_set -- for token-based algorithms:
    • True -- t and ttt is equal.
    • False (default) -- t and ttt is different.

Examples

For example, Hamming distance:

import textdistance

textdistance.hamming('test', 'text')
# 1

textdistance.hamming.distance('test', 'text')
# 1

textdistance.hamming.similarity('test', 'text')
# 3

textdistance.hamming.normalized_distance('test', 'text')
# 0.25

textdistance.hamming.normalized_similarity('test', 'text')
# 0.75

textdistance.Hamming(qval=2).distance('test', 'text')
# 2

Any other algorithms have same interface.

Articles

A few articles with examples how to use textdistance in the real world:

Extra libraries

For main algorithms textdistance try to call known external libraries (fastest first) if available (installed in your system) and possible (this implementation can compare this type of sequences). Install textdistance with extras for this feature.

You can disable this by passing external=False argument on init:

import textdistance
hamming = textdistance.Hamming(external=False)
hamming('text', 'testit')
# 3

Supported libraries:

  1. abydos
  2. Distance
  3. jellyfish
  4. py_stringmatching
  5. pylev
  6. python-Levenshtein
  7. pyxDamerauLevenshtein

Algorithms:

  1. DamerauLevenshtein
  2. Hamming
  3. Jaro
  4. JaroWinkler
  5. Levenshtein

Benchmarks

Without extras installation:

algorithm library function time
DamerauLevenshtein jellyfish damerau_levenshtein_distance 0.00965294
DamerauLevenshtein pyxdameraulevenshtein damerau_levenshtein_distance 0.151378
DamerauLevenshtein pylev damerau_levenshtein 0.766461
DamerauLevenshtein textdistance DamerauLevenshtein 4.13463
DamerauLevenshtein abydos damerau_levenshtein 4.3831
Hamming Levenshtein hamming 0.0014428
Hamming jellyfish hamming_distance 0.00240262
Hamming distance hamming 0.036253
Hamming abydos hamming 0.0383933
Hamming textdistance Hamming 0.176781
Jaro Levenshtein jaro 0.00313561
Jaro jellyfish jaro_distance 0.0051885
Jaro py_stringmatching jaro 0.180628
Jaro textdistance Jaro 0.278917
JaroWinkler Levenshtein jaro_winkler 0.00319735
JaroWinkler jellyfish jaro_winkler 0.00540443
JaroWinkler textdistance JaroWinkler 0.289626
Levenshtein Levenshtein distance 0.00414404
Levenshtein jellyfish levenshtein_distance 0.00601647
Levenshtein py_stringmatching levenshtein 0.252901
Levenshtein pylev levenshtein 0.569182
Levenshtein distance levenshtein 1.15726
Levenshtein abydos levenshtein 3.68451
Levenshtein textdistance Levenshtein 8.63674

Total: 24 libs.

Yeah, so slow. Use TextDistance on production only with extras.

Textdistance use benchmark's results for algorithm's optimization and try to call fastest external lib first (if possible).

You can run benchmark manually on your system:

pip install textdistance[benchmark]
python3 -m textdistance.benchmark

TextDistance show benchmarks results table for your system and save libraries priorities into libraries.json file in TextDistance's folder. This file will be used by textdistance for calling fastest algorithm implementation. Default libraries.json already included in package.

Running tests

All you need is task. See Taskfile.yml for the list of available commands. For example, to run tests including third-party libraries usage, execute task pytest-external:run.

Contributing

PRs are welcome!

  • Found a bug? Fix it!
  • Want to add more algorithms? Sure! Just make it with the same interface as other algorithms in the lib and add some tests.
  • Can make something faster? Great! Just avoid external dependencies and remember that everything should work not only with strings.
  • Something else that do you think is good? Do it! Just make sure that CI passes and everything from the README is still applicable (interface, features, and so on).
  • Have no time to code? Tell your friends and subscribers about textdistance. More users, more contributions, more amazing features.

Thank you ❤️

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].