F. Theory of Computation

摘要

Use what you understand well where you know little, by transforming that about which you know little into something embeddable in the well-understood corpus. Do the transformation with the lowest distortion possible. This is the heart of this important paper, applied to string and document comparison. The paper uses the language of discrete mathematics. It is not easy to read, but is certainly worth reading. L1 is a distance (metric) between two entities equal to the sum of the absolute values of the differences between corresponding coordinates of the entities. Many good algorithms exist for it. The edit or Levenstein distance measures the minimum number of character insertions, deletions, and substitutions needed to transform one string into the other. The edit distance is well defined even for strings of varying lengths. Improving the algorithms that use this distance is an important endeavor for both theoretical and practical reasons.