An approximate string matching approach for handling incorrectly typed urls

ABSTRACT

In this paper we approach the problem of providing corrections for incorrectly typed URLs. This problem is significantly different from the classical spelling correction problem. We describe our contribution - building a custom data structure and a search algorithm that can find approximate matches for incorrect URLs. We evaluate the quality of our results through experiments with analysts. Our system is now being used in the Google search engine.

REFERENCES

• 1: V.I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10(8):707--710, 1966.
• 2: Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
• 3: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford University, 1998.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Experimentation

Keywords:
url correction