Lattice Path Edit Distance: A R omanization-aware Edit Distance for Extracting Misspelling-Correction Pairs from J apanese Search Query Logs (2023)

Abstract: Edit distance has been successfully used to extract training data, i.e., misspelling-correction pairs, of spelling correction models from search query logs in languages including English. However, the success does not readily apply to Japanese, where misspellings are often dissimilar to correct spellings due to the romanization-based input methods. To address this problem, we introduce lattice path edit distance, which utilizes romanization lattices to efficiently consider all possible romanized forms of input strings. Empirical experiments using Japanese search query logs demonstrated that the lattice path edit distance outperformed baseline methods including the standard edit distance combined with an existing transliterator and morphological analyzer. A training data collection pipeline that uses the lattice path edit distance has been deployed in production at our search engine for over a year.

## introduction edit distance @xcite is indispensable for query spelling error correction, which is an essential component in modern search engines. training spelling correction models requires a huge amount of training data, i.e., misspelling-correction pairs, but creating such data by hand is costly. to address this problem, previous studies have automatically extracted misspellingcorrection pairs from query logs by using edit distance between two queries as a clue @xcite @xcite . in japanese, however, edit distance is not effective for detecting misspelling-correction pairs due to the unique input methods (ims) (c.f., section 2.1). in typical japanese ims, users first enter romanized text and then convert it into japanese characters. in the latter step, a typo can produce misspellings that are dissimilar to the correct * yahoo japan corporation at the time of submission. ## problems this section provides in-depth discussions on the problems to be addressed in this work. ## lattice path edit distance this section introduces the proposed lattice path edit distance, which is aware of romanized forms of input strings. ## experiment empirical experiments were conducted using japanese search query logs to investigate the quality of the misspelling-correction pairs extracted by using the lattice path edit distance. ## related work previous studies successfully used the levenshtein distance to extract misspelling-correction pairs from github's commit logs @xcite ) and wikipedia's revision history @xcite . although this may seem to contradict with our findings, these successes are reasonable because the text domains explored in those studies are substantially different from search query logs (appendix e). some studies @xcite investigated edit distance between representations of pronunciations as a clue for spelling variant extraction. @xcite deterministically converted input strings into romanized forms and then computed the edit distance between them. their approach is essentially the same as the romanization baseline explored in our experiment. synthetically generating misspellings from correct spellings, rather than extracting misspellingcorrection pairs from some linguistic resources (e.g., query logs), is another common approach to addressing the scarcity of training data for spelling error correction. it is interesting to see that this line of attempts has also emphasized the importance of considering pronunciations in parallel to this work @xcite . as discussed in appendix b, the lattice path edit distance is closely related to finite-state automata. the contributions of this work compared to the previous studies on finite-state automata are two folds. first, we explored a new application of finite-state automata to the misspelling-correction pair detection in japanese. second, we introduced a simplified variant of the @xcite that is tailored to the new application setting, where the input automata have lattice structures. ## conclusion and future work we have introduced lattice path edit distance, a romanization-aware edit distance, with a focus on extracting misspelling-correction pairs from japanese search query logs. a dp algorithm and its faster variant were proposed for the efficient computation of the lattice path edit distance. the empirical results demonstrated that the lattice path edit distance outperformed the standard edit distance even if an existing transliterator and morphological analyzer were employed together. although this work focused on japanese, similar problems are considered to arise in other asian languages that have their own ims. for example, the chinese language also has its own romanization system, pinyin, and language-specific ims based on it. application of the lattice path edit distance to such languages is a future direction worth exploring. to the damerau-levenshtein distance by adding another term min @xmath0,k ′ ∈px(k) @xmath1,l ′ ∈py(l) s.t. π x k ′ :@xmath2:j ∧π x k:@xmath3:l d[k ′ ][l ′ ] + 1 (7) to equation (3). a similar extension can also be made to algorithm 2.