Какой алгоритм расстояния между строками лучше всего подходит для измерения точности печати?
Я пытаюсь написать функцию, которая определяет, насколько точно пользователь набрал определенную фразу / предложение / слово / слова. Моя цель состоит в том, чтобы создать приложение для обучения точности набора текста определенными фразами.
Мой первоначальный инстинкт - использовать базовый алгоритм расстояния Левенштейна (в основном потому, что это единственный алгоритм, который я знал на макушке).
Но после небольшого исследования я увидел, что Jaro-Winkler - немного более интересный алгоритм из-за его рассмотрения для транспозиций.
Я даже нашел ссылку, которая говорит о различиях между этими алгоритмами:
Разница между Яро-Винклером и Левенштейном?
Прочитав все это, в дополнение к соответствующим постам в Википедии, я все еще немного не понимаю, какой алгоритм лучше всего соответствует моей цели.
3 ответа
Поскольку вы оцениваете качество печати и хотите научить студента совершать ноль ошибок, вы должны использовать расстояние Левенштейна, потому что оно менее прощающее.
Кроме того, оценка Левенштейна является более интуитивной для понимания и более легкой для графического представления, чем результаты Jaro-Winkler. Вы можете изменить алгоритм Левенштейна, чтобы сообщать о вставках, удалениях и опечатках отдельно и показывать конечным пользователям список исправлений. Jaro-Winkler, с другой стороны, дает вам счет, который трудно показать конечному пользователю, потому что штрафы за опечатку в середине ниже, чем штрафы в конце.
Немного насмешливый, но только немного: создайте генеративную модель для набора текста, которая дает высокую (предыдущую) вероятность нажатия правой буквы, и распределите некоторые вероятности одновременного нажатия двух соседних клавиш, двух ключей от разных рук в неправильный порядок, два ключа от одной и той же руки в неправильном порядке, ключ рядом с правильным, ключ далеко от правильного и т. д. Или, возможно, менее однозначно: предоставьте вашей модели вероятность для данной последовательности нажатий клавиш текущая пара ключей необходима для продолжения прохождения. Вы могли бы многое сделать с такой моделью; Например, вы можете получить метрику, подобную "расстоянию", дав оценку вероятности для фактической успеваемости учащегося. Но еще лучше было бы дать им отчет, в котором резюмируется, какие виды ошибок они совершают чаще всего - в конце концов, зачем сводить их производительность к одному числу, когда их будет много? Бонусные баллы, если вы узнаете вероятности для различных видов ошибок из большого корпуса работы настоящих машинисток.
Я в основном согласен с ответом, данным dasblinkenlight, однако предложил бы использовать расстояниеДамерау- Левенштейна вместо только Левенштейна, то есть включая транспозиции. Перестановки довольно часты и их легко выполнять при наборе текста, и нет веских причин, по которым они должны подвергаться двойному штрафу за расстояние по сравнению с другими возможными ошибками (вставками, удалениями и подстановками).