{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T19:53:16Z","timestamp":1674676396543},"reference-count":34,"publisher":"MIT Press - Journals","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2004,12]]},"abstract":" The need to correct garbled strings arises in many areas of natural language processing. If a dictionary is available that covers all possible input tokens, a natural set of candidates for correcting an erroneous input P is the set of all words in the dictionary for which the Levenshtein distance to Pdoes not exceed a given (small) bound k. In this article we describe methods for efficiently selecting such candidate sets. After introducing as a starting point a basic correction method based on the concept of a \u201cuniversal Levenshtein automaton,\u201d we show how two filtering methods known from the field of approximate text search can be used to improve the basic procedure in a significant way. The first method, which uses standard dictionaries plus dictionaries with reversed words, leads to very short correction times for most classes of input strings. Our evaluation results demonstrate that correction times for fixed-distance bounds depend on the expected number of correction candidates, which decreases for longer input words. Similarly the choice of an optimal filtering method depends on the length of the input words. <\/jats:p>","DOI":"10.1162\/0891201042544938","type":"journal-article","created":{"date-parts":[[2004,11,25]],"date-time":"2004-11-25T23:14:47Z","timestamp":1101424487000},"page":"451-477","source":"Crossref","is-referenced-by-count":42,"title":["Fast Approximate Search in Large Dictionaries"],"prefix":"10.1162","volume":"30","author":[{"given":"Stoyan","family":"Mihov","sequence":"first","affiliation":[{"name":"Bulgarian Academy of Sciences, Linguistic Modelling Department, Institute for Parallel Processing, Bulgarian Academy of Sciences, 25A, Akad. G. Bonchev Str., 1113 Sofia, Bulgaria."}]},{"given":"Klaus U.","family":"Schulz","sequence":"additional","affiliation":[{"name":"University of Munich, Centrum f\u00fcr Informations-und Sprachverarbeitung, Ludwig-Maximilians-Universit\u00e4t-M\u00fcnchen, Oettingenstr. 67, 80538 Munchen, Germany."}]}],"member":"281","reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(83)90022-5"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001495000389"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009253"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(60)90272-2"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1162\/089120100561601"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1145\/366862.366913"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001495000080"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1142\/9789812830968_0008"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90138-6"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380240105"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1145\/146370.146380"},{"key":"p_16","first-page":"707","volume":"10","author":"Levenshtein Vladimir I","year":"1966","journal-title":"Soviet Physics-Doklady"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185432"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00121-0"},{"key":"p_24","first-page":"261","volume":"1","author":"Odell Margaret K","year":"1918","journal-title":"Patent Number"},{"key":"p_25","first-page":"435","volume":"1","author":"Odell Margaret K","year":"1992","journal-title":"Patent Number"},{"issue":"1","key":"p_26","first-page":"73","volume":"22","author":"Oflazer Kemal","year":"1996","journal-title":"Computational Linguistics"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(96)00101-X"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380180407"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223255"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1007\/s10032-002-0082-8"},{"key":"p_32","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(95)00102-6"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(90)90070-2"},{"key":"p_35","doi-asserted-by":"publisher","DOI":"10.1145\/357423.357428"},{"key":"p_37","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(90)90023-E"},{"key":"p_38","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"p_39","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90023-9"},{"key":"p_40","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90143-4"},{"key":"p_41","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/20.2.141"},{"key":"p_42","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"p_44","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(90)90071-R"},{"key":"p_45","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135244"},{"key":"p_46","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380250307"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/0891201042544938","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:42:17Z","timestamp":1615585337000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/30\/4\/451-477\/1863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,12]]}},"alternative-id":["10.1162\/0891201042544938"],"URL":"https:\/\/doi.org\/10.1162\/0891201042544938","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,12]]}}}