Deduplication Method for Ukrainian Last Names, Medicinal Names, and Toponyms Based on Metaphone Phonetic Algorithm

摘要

This paper attempts to optimize the phonetic search processes for fuzzy matching tasks, such as deduplication of data in various databases and registers to reduce the number of errors in personal data entry (for instance, last names). The analysis of the most common last names in the territory of Ukraine shows that the majority of these last names are of Ukrainian and Russian origin (which are also reduced to phonetic rules of the Ukrainian language). The rules for pronouncing and writing last names in Ukrainian are fundamentally different from the basic algorithms for English and quite different for the Russian language, so the phonetic algorithm should take into account the peculiarities of the formation of Ukrainian last names. The use of the phonetic algorithm gives significant advantages in search and deduplication in comparison with already known algorithms: calculation of Levenshtein, Damerau-Levenshtein, Hamming, Jaro or Jaro-Winkler distance, Q-gram index, etc. [1]. The task of searching by last name was previously formalized in English [2, 3], Russian [4, 5] and some other languages, but for the Ukrainian language such an attempt was made for the first time. The paper presents the results of the experiment on the formation of phonetic indices, as well as the results of increasing productivity when using the generated indices. A method of tailoring the search to other domains and several related languages is presented separately, for example, the search for medicines. Also, search optimization by place names in Ukrainian and Russian was separately worked out. Since in Ukraine there is an abrupt change in the names of cities and streets, the latest relevant data was collected to obtain an up-to-date list of names. Among the existing phonetic search algorithms for the Cyrillic language group, the Metaphone has proven itself in the best way.