Мы разрабатываем систему для нечеткого сопоставления более чем 50 международных языков с использованием стандарта символов Unicode UTF-8, UTF-16 и UTF-32. До сих пор мы могли использовать расстояние Левенштейна для обнаружения ошибок в написании слов с расширенными символами немецкого языка Unicode.
Мы хотели бы расширить эту систему для обработки иероглифов китайского языка, представленных в Unicode. Как бы мы выполнили расчет расстояния Левенштейна между похожими китайскими иероглифами?
Во-первых, просто поясню: китайский иероглиф как таковой не эквивалентен немецкому или английскому слову. Большинство вещей, которые вы считаете словами (используя семантическое или синтаксическое определение слова), состоят из 1-3 символов. К таким последовательностям символов легко применить расстояние Левенштейна, представив их как последовательности кодовых точек UCS-2 или UCS-4. Поскольку большинство слов короткие (особенно слова длиной 1 или 2 символа), их использование может быть ограничено.
Однако, поскольку ваш вопрос конкретно касается расстояния редактирования между отдельными символами, я считаю, что требуется другой подход, и это может быть действительно очень сложно.
Для начала вам нужно представить каждый символ как последовательность компонентов/штрихов, из которых он состоит. Есть две проблемы:
Некоторые компоненты сами состоят из еще более мелких компонентов, поэтому однозначного определения того, как разбить символ на "атомарные" компоненты, нет. Если вы сделаете это на уровне отдельных штрихов, вам потребуется характеристика каждого отдельного штриха (положение внутри символа, форма, направление и т. д.). Я не думаю, что кто-либо, как и все, сделал это (мне было бы очень интересно, если бы кто-нибудь сказал мне обратное).
Вам нужно расположить штрихи или компоненты в порядке. Очевидным кандидатом является канонический порядок черт иероглифа, описанный в lexica, и даже есть веб-сайты со словарями с анимированными диаграммами порядка штрихов. Однако известные мне источники данных (для японского) генерируют эти анимации как последовательности растровой графики; Я никогда не видел считываемых человеком или машиной кодов, которые представляли бы последовательность штрихов (или даже имена отдельных штрихов) в форме, пригодной для расчета расстояния редактирования.
И последнее, что вы можете попробовать, это визуализировать глифы символа и рассчитать расстояние редактирования на основе сколько пикселей (или векторов) нужно изменить, чтобы превратить один символ в другой. символ в другой. Однажды я сделал это для латинских символов и комбинаций символов (на основе пикселей) в контексте посткоррекции OCR, и результаты были весьма обнадеживающими.
Быстрый ответ на комментарий Ларсмана ниже: в стандарте Unicode определены две связанные концепции (ниже я ссылаюсь на версия 6.0, глава 12):
Последовательности идеографического описания (раздел 12.2): Unicode определяет кодовые точки для основных компонентов символов (большинство из них в любом случае могут сами использоваться как отдельные символы), и существуют кодовые точки, используемые для склеивания их вместе для формирования последовательности компонентов, описывающих композиция более сложного характера. Таким образом, это работает аналогично объединению символов, но есть важные отличия:
Стандарт предлагает использовать последовательности идеографического описания для описания сложных или редких символов, которые не представлены какой-либо существующей кодовой точкой; но он явно не рекомендует использовать последовательности описания вместо обычных символов:
В частности, последовательности идеографического описания не должны использоваться для предоставления альтернативных графических представлений закодированных идеограмм при обмене данными. В этом случае поиск, сопоставление и другие текстовые операции, основанные на содержимом, завершатся сбоем.
Я написал пакет Python fuzzychinese для исправления опечаток в китайских словах.
Как сказал @jogojapan, если вы действительно хотите рассчитать расстояние Левенштейна, имеет смысл использовать структуры подсимволов, такие как радикалы или штрихи. Вы можете использовать классы Stroke() или Radical() из fuzzychinese, чтобы разбить символы, а затем вычислить расстояние Левенштейна.
Однако я не уверен, что расстояние Левенштейна хорошо работает для исправления орфографических ошибок в китайских словах. В пакете, который я написал, я вычислил вектор tf–idf для штрихов n-грамм и использовал косинусное сходство для сопоставления слов.
char16_t, и он должен быть достаточно большим, чтобы вместить их все. - person obataku schedule 12.09.2012