A Best-First Anagram Hashing Filter for Approximate String Matching with Generalized Edit Distance

Malin Ahlberg, Gerlof BoumaCOLING 2012

TL;DR

This paper introduces a novel "best-first" anagram hashing filter that significantly speeds up approximate string matching by efficiently pre-filtering large lexicons. This method is particularly effective for generalized edit distances, where different edit operations have varying costs, making it suitable for historical texts and other applications with complex spelling variations.

What Problem Does This Paper Address?

Matching words in a text to a dictionary is a fundamental task in natural language processing. Often, the words in the text might not exactly match dictionary entries due to typos, historical spelling variations, or OCR errors. This is known as approximate string matching. A common way to measure the "closeness" of two strings is using edit distance, which counts the minimum number of operations (insertions, deletions, substitutions) to transform one string into another.

However, calculating edit distance for every word in a large corpus against every word in a large dictionary is computationally prohibitive. Existing methods, like the anagram hashing filter, help by quickly discarding unlikely matches. But these methods often struggle with "generalized edit distance," where different types of edits have different costs (e.g., substituting 'th' for 'þ' might be cheaper in historical texts than substituting 'a' for 'z'). This paper tackles the challenge of efficiently performing approximate string matching with these more nuanced, weighted edit distances, especially for large-scale applications.

Methods

The core contribution is a best-first anagram hashing filter. This is an adaptation of a previously proposed anagram hashing filter. Here's what's new:

  • Best-First Search: Instead of exhaustively exploring all possible edit permutations up to a certain number of edits, the filter uses a best-first search strategy. This means it prioritizes exploring paths that are most likely to lead to a good match, based on the estimated cost. This is crucial for generalized edit distance, where the "cost" is not just the number of edits but their weighted sum.
  • Incorporating Weighted Rules: The filter directly incorporates the costs of weighted substitution rules into its search. This allows it to prune the search space much more effectively than methods that only consider the number of edits.
  • Optimistic Cost Estimation: The filter uses an optimistic cost estimate for potential matches. This means it might sometimes overestimate the cost, but it guarantees that it won't miss any potential matches within the specified cost cutoff.
  • Bitmap Tracking: To efficiently handle overlapping substitutions and avoid redundant computations, the algorithm uses bitmaps to track which characters in the source string have been "used" by a substitution. This is essential for restricted edit distance where substitutions cannot overlap.
  • Rule Fusion: The paper also describes a technique to fuse similar substitution rules, reducing redundancy and improving efficiency.

The standard component is the underlying anagram hashing mechanism, which assigns hash values to strings based on character sums raised to a power. This allows for quick, albeit optimistic, estimations of edit distance.

Datasets

The experiments were conducted using:

  • A real-world dataset of Old Swedish texts: This corpus comprised 162,000 unique word types and 3 million tokens.
  • A combination of three Old Swedish dictionaries: These provided a lexicon of 54,000 entries.
  • The corpus itself as a lexicon: In some experiments, the corpus tokens were used as the target vocabulary to test the impact of larger lexicons.
  • 6045 weighted substitution rules: These rules were of the form n → m, where n and m could be uni-, bi-, or trigrams, and were derived from the literature.

The paper does not introduce a new benchmark dataset but rather uses existing historical text data and established rule sets.

Key Insights and Ideas

  • Best-first search is key for weighted edits: The paper demonstrates that a best-first search strategy is significantly more effective than exhaustive search when dealing with generalized edit distances, as it intelligently navigates the complex cost landscape.
  • Efficiency gains are substantial: The proposed filter dramatically reduces the number of candidates that require expensive exact edit distance calculations, making large-scale approximate matching feasible.
  • Performance is sensitive to parameters: The running time and effectiveness of the filter are highly dependent on the chosen "stopping criteria" (e.g., finding the best match vs. top k matches) and the "cutoff point" (maximum allowed edit cost).
  • Lexicon size matters: While the filter itself is independent of the lexicon size, a larger lexicon naturally increases the chance of finding more potential matches, which can lead to more expensive exact calculations and thus impact overall performance.

Key Results

  • The best-first anagram hashing filter significantly speeds up approximate string matching. For example, matching all 162k types against a 54k entry dictionary with a cutoff of 1.5 took approximately 106 minutes (25 types/s, 85 tokens/s).
  • The filter accounts for a substantial portion of the running time (20-60%), highlighting its importance in the overall system.
  • Even with a large rule set (6045 rules) and a million-word corpus, the system achieves throughputs suitable for off-line processing.
  • The number of exact edit distance calculations triggered by the filter is drastically reduced compared to a full search. For instance, with a cutoff of 1.5, the filter returned an average of 22 hashes (no duplicates) per type that triggered exact calculations, out of an average of 194 rules fused from 450 applicable substitutions.
  • Increasing the cutoff value (e.g., from 1.5 to 2.0) leads to a significant increase in running time, as more potential matches need to be explored.

Limitations and Future Work

  • Optimistic Nature: The filter's optimistic cost estimation means it might miss some very good matches if their estimated cost is too high, although this is mitigated by the best-first search and bitmap tracking.
  • Restricted Edit Distance: The current implementation focuses on restricted edit distance, where substitutions cannot overlap. Extending it to unrestricted edit distance (where edits can overlap) is a significant area for future work.
  • Algorithmic Improvements: The authors suggest further research into how dependencies between rules are tracked, as the Cartesian product of bitmap sets can cause overhead. Investigating ways to extend the filter to handle context-specific edits or edits that are not formally part of the substitution is also proposed.
  • Non-finite Target Vocabularies: The current anagram hash filter approach is not well-suited for non-finite target vocabularies (e.g., those involving productive compounding), unlike automaton-based approaches.

Summary updated

BibTeX
@inproceedings{ahlberg2012best,
  author = {Malin Ahlberg and Gerlof Bouma},
  title = {{A Best-First Anagram Hashing Filter for Approximate String Matching with Generalized Edit Distance}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2012},
}
Figure