RUS  ENG
Полная версия
ЖУРНАЛЫ // Программные системы: теория и приложения // Архив

Программные системы: теория и приложения, 2018, том 9, выпуск 4, страницы 579–596 (Mi ps329)

Математические основы программирования

Устойчивая оценка качества алгоритмов сходства символьных строк и их нормализаций

С. В. Знаменский

Институт программных систем им. А. К. Айламазяна РАН

Аннотация: Выбор средств поиска скрытой общности в данных новой природы требует устойчивых и воспроизводимых сравнительных оценок качества абстрактных алгоритмов близости символьных строк. Обычные оценка на основе искусственно сгенерированных или вручную размеченных тестов существенно разнятся, надёжнее оценивая метод этой искусственной генерации по отношению к алгоритмам сходства, а оценки на базе данных пользователей не могут быть точно воспроизведены.
Предложена простая, прозрачная, объективная и воспроизводимая численная оценка качества метрики на строках. Используются параллельные тексты переводов книг на разные языки. Качество меры оценивается процентом ошибок в возможных различных попытках определения перевода данного абзаца среди двух абзацев книги на другом языке, один из которых действительно является переводом. Устойчивость оценок верифицируется независимостью от выбора книги и пары языков.
Численный эксперимент устойчиво отранжировал по качеству абстрактные алгоритмы сравнения символьных строк и показал сильную зависимость от выбора нормализации.

Ключевые слова и фразы: сходство строк, анализ данных, метрика подобия, метрика расстояния, числовая оценка, оценка качества.

УДК: 519.652.3

Поступила в редакцию: 17.04.2018
03.12.2018
Подписана в печать : 28.12.2018

DOI: 10.25209/2079-3316-2018-9-4-579-596



© МИАН, 2024