I found the following article<\/a> written by Nick Johnson about the use of finite state machines for approximate\u00a0 string matches i.e. string matches which are not exact but bound by a given edit distance. The algorithm is based on so called “Levenshtein automatons”. Those automatons are inspired by the construction of the Levenshtein matrix used for edit distance computations. For more information start reading the WP-article about the Levenshtein algorithm<\/a> which provides sufficient background for Nicks article.<\/p>\n I downloaded the code from github and checked it out but was very stunned about the time it took for the automaton construction once strings grow big. It took almost 6 minutes on my 1.5 GHz notebook to construct the following Levenshtein automaton:<\/p>\n The algorithm is advertised as a “damn cool algorithm” by the author but since the major effect on my notebook was producing heat I wonder if “cool” shouldn’t be replaced by “hot”?<\/p>\n In the following article I’m constructing an approximate string matching algorithm from scratch.<\/p>\n Let ‘`S` be a string with `len(S)=n` and `k` a positive number with `k`<=`n`. By “?” we denote a wildcard symbol that matches any character including no character ( expressing a contraction ). Since S has length `n` we can select arbitrary `k` indexes in the set `{0,…,n-1}` and substitute the characters of `S` at those indexes using a wildcard symbol. If for example (S = “food” , k = 1 and index = 2) we get “fo?d”.<\/p>\n We describe the rule which describes all possible character substitutions in “food” like this:<\/p>\n Applying successive left factorings yields:<\/p>\n This inspires a recursive notation which roughly looks like this:<\/p>\n or more precisely:<\/p>\n where we have used a string variable S instead of the concrete string “food”.<\/p>\n When using an arbitrary `k` instead of a fixed k = 1 we get the following recursive equations:<\/p>\n When we try to find an efficient implementation for the `pattern` function described above we need an interpretation of the `?` wildcard action. It can consume a character and feed the rest of the string into a new call of `pattern` or skip a character and do the same with the rest. Since we cannot decide the choice for every string by default we eventually need backtracking but since we can memoize intermediate results we can also lower efforts. But step by step …<\/p>\n The basic idea when matching a string `S1` against a string `S2` is that we attempt to match `S1[0]` against `S2[0]` and when we succeed, we continue matching `S[1:]` against `S2[1:]` using the same constant `k`. If we fail, we have several choices depending on the interpretation of the wildcard action: it can consume a character of S2 or leave S2 as it is. Finally S1 and S2 are exchangeable, so we are left with the following choices:<\/p>\n All of those choices are valid and if one fails we need to check out another one. This is sufficient for starting a first implementation.<\/p>\n The following implementation is a good point to start with:<\/p>\n The algorithm employs full backtracking and it is also limited to medium sized strings ( in Python ) because of recursion. But it shows the central ideas and is simple.<\/p>\n Our second implementation still uses recursion but introduces a dictionary which records all `(i,j)` index pairs that have been encountered and stores the current value of `k`. If the algorithm finds a value `k'` at `(i,j)` with `k'`<=`k` it will immediately return `False` because this particular trace has been unsuccessfully checked out before. Using an` n x n` matrix to memoize results will reduce the complexity of the algorithm which becomes `O(n^2)` where n is the length of the string. In fact it will be even `O(n)` because only a stripe of width 2k along the diagonal of the (i,j)-matrix is checked out. Of course the effort depends on the constant k.<\/p>\n In our third and final implementation we eliminate the recursive call to `fuzzy_compare` and replace it using a stack containing tuples `(i, j, k)` recording the current state.<\/p>\n This is still a nice algorithm and it should be easy to translate it into C or into JavaScript for using it in your browser. Notice that the sequence of `if` ... `elif` branches can impact performance of the algorithm. Do you see a way to improve it?<\/p>\n When D is the Levenshtein distance between two strings S1 and S2 then `fuzzy_compare(S1, S2, k)` shall be `True` for `k`>`=D` and `False` otherwise. So when you want to test `fuzzy_compare` compute the Levenshtein distance and check `fuzzy_compare` with the boundary values `k = D` and `k = D-1`.<\/p>\n For exhaustive testing we define a set of strings as follows:<\/p>\n Given a prescribed n we define the set of strings of length = n which consists of \"a\" and \"b\" characters only. The number of those strings is 2^n. If we consider all pairs of strings in that set we get 2^(2n) of such pairs. Of course we could exploit symmetries to remove redundant pairs but in order to keep it simple we examine only small strings e.g. n = 6 which leads to 4096 pairs altogether.<\/p>\n Our test function is short:<\/p>\n Have much fun!<\/p>\n","protected":false},"excerpt":{"rendered":" A damn hot algorithm I found the following article written by Nick Johnson about the use of finite state machines for approximate\u00a0 string matches i.e. string matches which are not exact but bound by a given edit distance. The algorithm … Continue reading k = 6\r\nS\u00a0 = \"\".join(str(s) for s in range(10)*k)\r\nlev = levenshtein_automata(S, k).to_dfa()<\/pre>\n
Recursive rules for approximate string matching<\/h3>\n
pattern(food, 1) = ?ood | f?od | fo?d\u00a0 | foo?<\/pre>\n
pattern(food, 1) = ?ood | f\u00a0 ( ?od | o (?d\u00a0 | o? ) )<\/pre>\n
pattern(food, 1) = ?ood | f pattern(ood, 1)<\/pre>\n
pattern(c, 1) = ?\r\npattern(S, 1) = ?S[1:] | S[0] pattern(S[1:], 1)<\/pre>\n
pattern(c, k) = ?\r\npattern(S, k) = ?pattern(S[1:], k-1) | S[0] pattern(S[1:], k)<\/pre>\n
Consuming or not consuming?<\/h3>\n
fuzzy_compare(S1, S2[1:], k-1)\r\nfuzzy_compare(S2, S1[1:], k-1)\r\nfuzzy_compare(S1[1:], S2[1:], k-1)<\/pre>\n
A first implementation<\/h3>\n
def fuzzy_compare(S1, S2, k, i=0, j=0):\r\n N1 = len(S1)\r\n N2 = len(S2)\r\n while True:\r\n if N1-i<=k and N2-j<=k:\r\n return True\r\n try:\r\n if S1[i] == S2[j]:\r\n i+=1\r\n j+=1\r\n continue\r\n except IndexError:\r\n return False\r\n if k == 0:\r\n return False\r\n else:\r\n if fuzzy_compare(S1, S2, k-1, i+1, j):\r\n return True\r\n if fuzzy_compare(S1, S2, k-1, i, j+1):\r\n return True\r\n if fuzzy_compare(S1, S2, k-1, i+1, j+1):\r\n return True\r\n return False<\/pre>\n
A second implementation using memoization<\/h3>\n
def is_visited(i, j, k, visited):\r\n m = visited.get((i,j),-1)\r\n if k
A third implementation eliminating recursion<\/h3>\n
def is_visited(i, j, k, visited):\r\n m = visited.get((i,j),-1)\r\n if k
Checking the algorithm<\/h3>\n
def levenshtein(s1, s2):\r\n l1 = len(s1)\r\n l2 = len(s2)\r\n matrix = [range(l1 + 1)] * (l2 + 1)\r\n for zz in range(l2 + 1):\r\n matrix[zz] = range(zz,zz + l1 + 1)\r\n for zz in range(0,l2):\r\n for sz in range(0,l1):\r\n if s1[sz] == s2[zz]:\r\n matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1,\r\n matrix[zz][sz+1] + 1,\r\n matrix[zz][sz])\r\n else:\r\n matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1,\r\n matrix[zz][sz+1] + 1,\r\n matrix[zz][sz] + 1)\r\n return matrix[l2][l1]<\/pre>\n
def string_set(S = None, k = 0, strings = None, n = 6):\r\n if S is None:\r\n strings = []\r\n S = [\"a\"]*n\r\n strings.append(\"\".join(S))\r\n for i in range(k, n):\r\n S1 = S[:]\r\n S1[i] = \"b\"\r\n strings.append(\"\".join(S1))\r\n string_set(S1, i+1, strings, n)\r\n return strings\r\n\r\ndef string_pairs(n):\r\n L1 = string_set(n=n)\r\n pairs = []\r\n for i in range(len(L1)):\r\n for k in range(1, n+1):\r\n L2 = string_set(n=k)\r\n for j in range(len(L2)):\r\n pairs.append((L1[i],L2[j],levenshtein(L1[i], L2[j])))\r\n pairs.append((L2[j],L1[i],levenshtein(L2[j], L1[i])))\r\n return pairs<\/pre>\n
def test(n):\r\n for S1, S2, D in string_pairs(n):\r\n assert fuzzy_compare(S1, S2, D) == True, (S1, S2, D)\r\n assert fuzzy_compare(S1, S2, D-1) == False, (S1, S2, D-1)<\/pre>\n