%0 Conference Proceedings %T Fast Approximate String Matching with Suffix Arrays and A* Parsing %A Koehn, Philipp %A Senellart, Jean %S Proceedings of the 9th Conference of the Association for Machine Translation in the Americas: Research Papers %D 2010 %8 oct 31 nov 4 %I Association for Machine Translation in the Americas %C Denver, Colorado, USA %F koehn-senellart-2010-fast %X We present a novel exact solution to the approximate string matching problem in the context of translation memories, where a text segment has to be matched against a large corpus, while allowing for errors. We use suffix arrays to detect exact n-gram matches, A* search heuristics to discard matches and A* parsing to validate candidate segments. The method outperforms the canonical baseline by a factor of 100, with average lookup times of 4.3–247ms for a segment in a realistic scenario. %U https://aclanthology.org/2010.amta-papers.2