Выбор варианта из множества решений при нечетком сравнении строк

Ирина Евгеньевна Воронина; Никита Андреевич Экерт

doi:10.17308/sait/1995-5499/2023/2/181-191

Ирина Евгеньевна Воронина Воронежский государственный университет https://orcid.org/0000-0003-0040-5764
Никита Андреевич Экерт Воронежский государственный университет https://orcid.org/0009-0005-8176-8226

DOI: https://doi.org/10.17308/sait/1995-5499/2023/2/181-191

Ключевые слова: нечеткое сравнение строк, редакционное расстояние Левенштейна, редакционное расстояние Дамерау — Левенштейна, расстояние Джаро — Винклера, расстояние Хэмминга, исправление опечаток, исправление орфографических ошибок

Аннотация

Рассматривается актуальная проблема исправления опечаток и орфографических ошибок при анализе комментариев в социальных и корпоративных сетях. В качестве предмета исследования выбраны алгоритмы нечеткого сравнения строк, а именно алгоритмы поиска редакционного расстояния Левенштейна, Дамерау — Левенштейна, Джаро — Винклера и Хемминга. Проводится сравнение скорости работы методов и оценка их алгоритмической сложности. Предлагается метод контекстно-независимого выбора варианта из множества решений при нечетком сравнении строк. Сформированы гипотезы, релевантность которых доказана в результате выполнения вычислительного эксперимента. В качестве оценки предлагаемого линейного алгоритма приведена метрика точности. Теоретическая значимость исследования заключается в приведении оценки качества существующих алгоритмов нечеткого сравнения строк и выдвижения гипотез с целью разработки алгоритма исправления опечаток и орфографических ошибок в тексте. Практическая значимость заключается в программной реализации алгоритма исправления опечаток и орфографических ошибок в тексте, а также в проведении вычислительного эксперимента с получением словаря частотности замен символов. Новизна результата заключается в разработке реализации алгоритма решения задачи исправления опечаток и орфографических ошибок, отличающегося высокими показателями качества работы.

Скачивания

Данные скачивания пока не доступны.

Биографии авторов

Ирина Евгеньевна Воронина, Воронежский государственный университет

д-р техн. наук, доц., профессор кафедры программного обеспечения и администрирования информационных систем Воронежского государственного университета

Никита Андреевич Экерт, Воронежский государственный университет

аспирант кафедры программного обеспечения и администрирования информационных систем Воронежского государственного университета

Литература

1. Phong Minh Vu [et al.] (2015) Mining User Opinions in Mobile App Reviews: A Keyword-based Approach. Computer Science Department Utah State University. P. 11.
2. Nikolaev I., Mitrenina O. and Lando T. (2016) Applied and Computational Linguistics. Moscow : URSS, 2016. 320 p.
3. DeepPavlov Documentation: comparison of the competition results SpellRuEval. – URL
4. Ingersoll G., Morton T. and Farris A. (2015) Taming Text. How to find, organize, and manipulate it. Manning Shelter Island, 2015. P 414.
5. Wegner P. (1960) A technique for counting ones in a binary computer. Communications of the ACM. Vol. 3, No 5. P. 322.
6. Levenshtein V. (1965) Binary codes with patches, inserts and substitutions. Reports of the USSR Academy of Sciences. Vol. 163, No 4. P. 845–848.
7. Veena G. and Jalaja G. (2015) Levenshtein Distance based Information Retrieval. International Journal of Scientific & Engineering Research. Vol. 6, No 5. P. 112–116.
8. Schulz K. and Mihov S. (2002) Fast string correction with Levenshtein automata. International Journal on Document Analysis and Recognition. Vol. 5, No 1. P. 67–85.
9. Kutuzov A. (2013) Improving English-Russian sentence alignment through POS tagging and Damerau-Levenshtein distance. National Research University Higher School of Economics. P. 63–68.
10. Jaro M. (1989) Advances in record linkage methodology as applied to the 1985 census of Tampa Florida. Journal of the American Statistical Association. Vol. 84, No 406. P. 414–420.
11. Winkler W. (1990) String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage . American Statistical Association. P. 354–359.
12. Winkler W. (2006) Overview of Record Linkage and Current Research Directions. Statistical Research Division. P. 44.
13. Papadatou-Pastou M. [et al.] (2020) Human handedness: A meta-analysis. Psychological Bulletin. No 146(6). P. 481–524.
14. Voronina I. (2007) Computer modeling of linguistic objects: monograph. Voronezh : Publishing and printing center of Voronezh State University. 177 p.
15. Zaliznyak A. (2022) Grammatical dictionary of Russian language. 6-th edition, reprint. Moscow : AST-Press. 800 p.
16. Kanerva J., Ginter F. and Salakoski T. (2020) Universal Lemmatizer: A Sequence-to-Sequence Model For Lemmatizing Universal Dependencies Treebanks. TurkuNLP Group, Department of Future Technologies, University of Turku, Finland. P. 24.