grapheditdistance 0.1.0

A edit distance edition based on graphs.

graph-edit-distance

A set of edit distance edition methods based on graphs. These methods allow to calculate the edition cost of an entity (for example a word or text), among a big quantity of terms with less computational cost than the usual methods.

At the moment, only normal and weighted Levenshtein algorithm are developed, but it is very easy to add new algorithms thanks to the project structure.

Install

pip install grapheditdistance

How to use

Although you can use all type of sequences of objects, which are hashable and comparable, with the class Graph, we are going to use the class TextGraph specially suited for text entities. You can create an edit distance graph with this command:

from grapheditdistance import TextGraph

g = TextGraph()

And next to add entities by two different methods: add()_ to add just one entity, and index() to add multiple entities at once.

# Adding entities individually
g.add('hi')
g.add('hello')
# Adding a sequence of entities
g.index(['bye', 'goodbye', 'point of sale', 'pointing'])

Finally, you can calculate the edition distance of a new word against all those previously added terms:

# Search the term with spelling mistakes "Poimt of sales"
results = g.search('Poimt of sales'.lower(), threshold=0.8, nbest=0)
# It should return
[(
    'point of sale',
    2.0,
    '[(None), (None), (None), (replace[m -> n], 1), (None), (None), (None), (None), (None), (None), \
    (None), (None), (None), (insert[s], 1), (Final)]'
)]

Where the first element of the tuple is the preprocessed entity, the second is the found entity, the third is the edition distance weight, and the last the list of edition operation applied to change the preprocessed query for obtaining the previously indexed one. This method will only return the entities which edition distance is less than the given threshold of 0.8 respect to the length of the original entity. That means, if the original entity has 15 character, the maximum number of errors is 3 (len(entity) * (1 - threshold)). You can limit the number of best results with the parameter nbest, 0 for no limit.

If you want an case insentive algorith, you can use str.lower() or _str.upper(). to preprocess both, the indexed entities and the searched entity. For example:

from grapheditdistance import TextGraph

TERMS = ['hello', 'bye', 'goodbye', 'point of sale', 'pointing']

# This is the same as the default parameter
g = TextGraph()
g.index([t.lower() for t in TERMS])
# Change the preprocess method
results = g.search('Poimt of sales'.lower(), threshold=0.8, nbest=0)
print(results)

# To use upper case instead lower case
g = TextGraph()
g.index([t.upper() for t in TERMS])
# Change the preprocess method
results = g.search('Poimt of sales'.upper(), threshold=0.8, nbest=0)
print(results)

# Do not use any entity preprocess
g = TextGraph()
g.index(TERMS)
# Change the preprocess method
results = g.search('Poimt of sales', threshold=0.75, nbest=0, )
print(results)

Changing the edit distance algorithm

You can easily to change the edit distance algorithm by the parameter distance. For example, instead of using the basic Levenshtein algorithm, you can use the weighted one, which that, you can define different weights for specific operation with given entity elements:

from grapheditdistance import TextGraph
from grapheditdistance.distances import WeightedLevenshtein

TERMS = ['hello', 'bye', 'goodbye', 'point of sale', 'pointing']

lev = WeightedLevenshtein()
lev.add_insert_cost(' ', 0.1)
lev.add_delete_cost(' ', 0.1)
lev.add_replace_cost(' ', '-', 0.1)
lev.add_replace_cost('-', ' ', 0.1)
tree = TextGraph(distance=lev)
tree.index([t.lower()  for t in TERMS])
results = tree.search('Poi ntof-sales'.lower(), nbest=1)
print(results)

Defining your own edit distance algorithm

In order to define you own algorithm, you only need to create a class from the super class EditDistance. For example:

from grapheditdistance.graph import BaseGraph
from grapheditdistance.operators import Operator
from grapheditdistance.distances import EditDistance
from typing import List, Sequence, Hashable

class MyEditDistanceAlgorithm(EditDistance):
    def max_cost(self) -> float:
        """
        :return: The maximum cost.
        """
        float_value = ...
        return float_value # The maximum possible cost.

    def costs(self,
              pos: int,
              entity: Sequence[Hashable],
              graph: BaseGraph,
              curr_node: int,
              next_node: int,
              operators: List[Operator]) -> List[Operator]:
        list_operators = ...
        return list_operators  # A new list of operators to arrive to next node. 

Where pos is the current position of the entity that we are evaluating; entity is the entity to compare with, the graph with all the system entities to compare against; curr_node is the current node in the graph; next_node is the next node we want to jump; operators are the list of operators to arrive to the current node.

The result should be the new operators to explore. For example, if to pass from node X to node Y we need to remove the character A, or to add the character B, or replace A by B, we need to return a list of three operators: [DeleteOperator(A), InsertOperator(B), ReplaceOperator(A, B)]. You can also add the operator NoneOperator() to indicate that passing from node X to Y does not require any costly operation, or FinalOperator() to indicate that we have already achieved the final node.

The available operators are in the package grapheditdistance.operator, however, you can define your own operators by inheriting from the class grapheditdistance.operator.Operator.

Other examples of use

At the moment, we have shown text edit distance examples. But, this algorithm can be used with other elements.

Phonetic symbols

You can use this algorithm with phonetic distance problems. For example:

from grapheditdistance import Graph
from grapheditdistance.distances import WeightedLevenshtein

# I use Graph() instead TextGraph() but with WeightedLevenshtein
lev = WeightedLevenshtein()
lev.add_replace_cost("ɛ", "ˈɛ", 0.1)
lev.add_replace_cost("ˈʊ", "ʊ", 0.1)
lev.add_replace_cost("aɪ", "ˈaɪ", 0.1)
g = Graph(distance=lev)
g.add(["h", "ˈɛ", "l", "əʊ"])
g.add(["h", "ɛ", "l", "ə", "ʊ"])
g.add(["ɡ", "ˈʊ", "d", "b", "ˈaɪ"])
g.add(["p", "ˈɔɪ", "n", "t", " ", "ɒ", "v", " ", "s", "e", "ɪ", "l"])
g.add(["p", "ˈɔɪ", "n", "t", "ɪ", "ŋ"])

# Search a variant of "hello"
term = ["h", "ɛ", "l", "əʊ"]
print(g.search(term))
# Prints: [(['h', 'ɛ', 'l', 'əʊ'], ['h', 'ˈɛ', 'l', 'əʊ'], 0.1, [(None), (replace[ɛ -> ˈɛ], 0.1), (None), (None), (Final)])]

Word level

You can also use this algorithm to use in a sequence of words instead of characters. For example, we can search if an entity exists giving very low cost value to add or remove stopwords:

from grapheditdistance.distances import WeightedLevenshtein
from grapheditdistance import Graph

lev = WeightedLevenshtein()
lev.add_delete_cost('of', 0.1)
lev.add_insert_cost('of', 0.1)
g = Graph(distance=lev)
g.add(['point', 'of', 'sales'])
g.add(['pointing'])
g.add(['reception', 'desk'])
print(g.search(['point', 'sales']))