string comparison

References

Summary

Question: given two strings, what can we say about their relationship?

In what follows, say our string lengths are m and n, with m ≤ n.

Exact Matching

Just check each character against each other

If we're going to compare the same strings over and over, we can first hash them

Hamming Distance

Given two strings of equal length, we can count the number of characters at which they differ

More generally, just pad the smaller string at the end, say, so they're the same length.

Levenshtein Distance

We allow strings to change by

  1. insertions
  2. deletions
  3. substitutions

This is relevant in bioinformatics

Complexity O(mn)

Jaro-Winkler Distance

Gives more weight to strings that match at the beginning

Suffix Trees

Contains all the suffixes of a given string

The nodes of the tree are all possible suffixes of a fixed string:

ex. DENIAL becomes a tree made up of

An edge of the tree corresponds to the possible endings of that node

ex. AABAAB will have an edge from AAB → AAB$ and one from AAB → AABA

But then we compress all of the chains

ex. since there's a single path AAB → AABA → AABAA → AABAAB, we compress this to AAB → AABAAB.

In implementation, you can just store the indices of a string, instead of repeatedly storing parts of the string.

Searching the tree is very convenient:

Substring Searches

Naive O(mn)

Knuth-Morris-Pratt O(m+n)

Boyer-Moore O(mn)

Rabin-Karp O(mn)