leven-search

Efficient and Flexible Searching Within Levenshtein Distance

Introduction

Welcome to Leven-Search, a library designed for efficient and fast searching of words within a specified Levenshtein distance.

This library is designed with Kaggle developers and researchers in mind as well as all others who deal with natural language processing, text analysis, and similar domains where the closeness of strings is a pivotal aspect.

What is Levenshtein Distance?

Levenshtein distance measures the difference between two sequences. In the context of strings, it is the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another.

For example, the Levenshtein distance between "table" and "marble" is 2:

• table → mable (substitution of t for `m')
• mable → marble (insertion of r)

Design Goals

The library is designed with the following goals in mind:

• Efficient indexing of large datasets of words. Indexing about 40k words from the Brown corpus takes about 300ms on a modern laptop, and the index takes about 53MB of RAM.
• Flexibility in searching. The library allows searching for words within a specified Levenshtein distance also allows configuring specific edit costs for each operation. It allows to configure other distances, like a keyboard distance.
• Extensibility. The library is designed to be easily extensible to support other edit distances, such as Damerau-Levenshtein distance or Jaro-Winkler distance.

Performance

Example performance of the library on a Brown corpus (only words larger than 2 characters) and a modern laptop:

Distance	Time per 1000 searches (in seconds)
0	0.0146
1	0.3933
1 (*)	0.4154
2	7.9556

(*) with the per-letter cost granularity

Installation

To install the library, simply run:

pip install leven-search

Usage

First, import the library:

import leven_search as lev

Then, create a LevenSearch object:

searcher = lev.LevenSearch()

Next, add words to the searcher:

searcher.insert("hello")
searcher.insert("world")

Finally, search for words within a specified Levenshtein distance:

searcher.find_dist("mello", 1)

Result:
	hello: ResultItem(word='hello', dist=1, updates=[m -> h])

Example

The following example shows how to use the library to search for words within a Brown corpus:

import nltk
import leven_search as lev

# Download the Brown corpus
nltk.download('brown')

# Create a LevenSearch object
searcher = lev.LevenSearch()

for w in nltk.corpus.brown.words():
  if len(w) > 2:
    searcher.insert(w)

# Search for words within a Levenshtein distance
searcher.find_dist('komputer', 1)

Result:
	computer: ResultItem(word='computer', dist=1, updates=[k -> c])

Search for words within a Levenshtein distance with custom costs

cost = lev.GranularEditCostConfig(default_cost=2, edit_costs=[lev.EditCost('k', 'c', 0.1)])
searcher.find_dist('komputer', 2, cost)

Result:
      computer: ResultItem(word='computer', dist=0.1, updates=[k -> c])

searcher.find_dist('yomputer', 2, cost)

Result:
      computer: ResultItem(word='computer', dist=2, updates=[y -> c])

searcher.find_dist('yomputer', 1, cost)

Result:
      None