Предложение по исправлению орфографии
Предложение исправления орфографии является частью программы, которая генерирует набор возможных замен для слов, вероятно, написанных с ошибками. Один из способов оценить правдоподобность этих замен — вычислить их редакционное расстояние относительно данного ошибочно написанного слова. Редакционное расстояние между двумя словами — это общее количество операций редактирования, необходимых для преобразования одного слова в другое. Обычно эти операции включают вставку, удаление и замену одного символа, а также перестановку 2 последовательных символов.
Например, для слова "wonder", если удалить символ 'o', получится "wnder". Если заменить 'o' на 'a', получится "wander". А если переставить "er", получится "wondre".
В этой стратегии редакционного расстояния степень сходства между двумя словами определяется их минимальным редакционным расстоянием. Если минимальное редакционное расстояние между word_1 и word_2 меньше, чем между word_1 и word_3, то word_1 более похоже на word_2, чем на word_3. Таким образом, word_2 является лучшим предложением по исправлению орфографии для word_1 по сравнению с word_3.
Предположим, что вы работаете в компании по разработке программного обеспечения, которой необходимо создать прототип программы предложений по исправлению орфографии. Этот прототип должен быть частью программного обеспечения для обработки текстов. Требование заключается в том, что он должен использовать стратегию редакционного расстояния для своих предложений по исправлению орфографии. Однако операция замены должна быть переопределена, чтобы соответствовать поведению опечатки. Стоимость замены одного символа другим зависит от их расположения на клавиатурной раскладке. Если они расположены близко друг к другу, стоимость составляет только половину от обычной. Для этой цели замена классифицируется на близкую замену и далекую замену. Их стоимости определены как 1 и 2 соответственно. А стоимости для вставки, удаления и перестановки составляют 2. Кроме того, эта программа должна работать достаточно быстро, чтобы уложиться в лимит времени, установленный вашим менеджером. Кстати, для этого прототипа выбрана английская клавиатурная раскладка QWERTY.
Цель
Сгенерировать оптимальные предложения по исправлению орфографии для каждого входного слова, где каждое оптимальное предложение по исправлению орфографии является словом в словаре, имеющим наименьшее минимальное редакционное расстояние от данного входного слова. Лимит времени для 5,000 ошибочно написанных слов составляет не более 5 минут.
Входные данные
Входные данные представляют собой стандартный ввод, который содержит 3 части данных. Каждая из этих трех частей заканчивается пустой строкой.
Первая часть — это набор правил близкой замены, где каждое правило хранится в одной строке. Каждая строка имеет два поля. Каждое поле разделено пробелом. Общее количество правил не превышает 150.
Первое поле — это символ, который может быть близко заменен другими символами.
Второе поле — это последовательность символов, которые могут быть близко заменены на символ из предыдущего поля. В этом поле нет пробелов.
Символы, которые могут содержаться в этой части, — это символы, которые можно ввести с помощью стандартной английской клавиатурной раскладки, включая буквенно-цифровые символы и некоторые знаки препинания без пробелов или табуляции. Они перечислены следующим образом.
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789' !@#$%^*()-_=+|[{]};:'”,<.>/?
Вторая часть — это последовательность слов в словаре, где каждое слово хранится в одной строке. Общее количество слов не превышает 150,000.
Символы в словаре — это буквенные символы с апострофом.
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ’
Третья часть — это последовательность слов, которые нужно проверить на наличие ошибок в написании. Каждое из этих слов также хранится в одной строке. Общее количество слов не превышает 5,000.
Символы, которые могут содержаться в этой части, такие же, как символы в первой части, включая буквенно-цифровые символы и некоторые знаки препинания. (См. первую часть.)
Поскольку каждая из этих трех частей заканчивается пустой строкой, третья пустая строка является завершением ввода.
Выходные данные
Для каждого слова в третьей части напишите строку, содержащую 3 части информации, разделенные двоеточием.
Первая часть — это данное входное слово.
Вторая часть — это минимальное редакционное расстояние между входным словом и предложенным словом(ами).
Третья часть — это отсортированная по возрастанию последовательность предложенных слов, разделенных пробелом. После последнего слова пробела нет.
Дополнительные объяснения
В этом примере входных данных есть 5 правил близкой замены (строки № 1-5), 10 слов в словаре (строки № 7-16) и 12 слов, для которых ищутся предложения (строки № 18-29).
В примере выходных данных есть 12 строк для каждого из соответствующих 12 слов из входных данных.
Для 1-го слова минимальное редакционное расстояние между x и его предложениями (A B Z a b) равно 2.
Все они являются (дальними) затратами на замену.
Для 2-го слова минимальное редакционное расстояние между s и его предложением (a) равно 1, что является стоимостью близкой замены, определенной 1-м правилом замены.
Для 3-го слова минимальное редакционное расстояние между z и его предложением (A Z a) равно 1, что является стоимостью близкой замены, определенной 1-м или 5-м правилом замены.
Для 4-го слова минимальное редакционное расстояние равно 4, что складывается из одной стоимости дальней замены и одной стоимости удаления.
Для 5-го слова минимальное редакционное расстояние равно 6. Затраты между xxx и (A B Z a b) складываются из двух удалений и одной дальней замены. Затраты между xxx и ABC складываются из трех дальней замен.
Для 6-го слова затраты между angre и anger складываются из одной стоимости перестановки. Затраты между angre и (angle angry) складываются из одной стоимости дальней замены.
Для 7-го и 8-го слова, кажется, они похожи. Но затраты для 7-го слова складываются из одной стоимости дальней замены. Но затраты между angrt и anger складываются из 2-х стоимостей близкой замены (r заменяется на e и t заменяется на r) согласно 4-му правилу близкой замены.
Для 9-го слова слово точно совпадает с словарем. Поэтому стоимость равна 0.
Для 10-го и 11-го слов каждая стоимость складывается из одной стоимости перестановки.
Для 12-го слова затраты между CAB и (A B) складываются из двух стоимостей удаления. Затраты между CAB и (ABC) складываются из одной стоимости удаления и одной стоимости вставки. Обратите внимание, что это не из-за 2-х перестановок CAB в ACB, а затем ACB в ABC.