c++ - чайников - фио по левенштейну



Как я могу определить расстояние Левенштейна для мандаринских иероглифов? (1)

Во-первых, просто для уточнения: китайский символ не является таким эквивалентом немецкого или английского слова . Большинство вещей, которые вы считаете словами (с использованием семантического или синтаксического определения «слова»), состоят из 1-3 символов. Прямо использовать расстояние Левенштейна до таких последовательностей символов, представляя их как последовательности кодовых точек UCS-2 или UCS-4. Поскольку большинство слов короткие (например, слова длиной 1 или 2 символа), это может быть ограниченным использованием.

Однако, поскольку ваш вопрос конкретно касается расстояния редактирования между отдельными персонажами , я считаю, что требуется другой подход, и это может быть очень сложно.

Для начала вам придется представлять каждый символ в виде последовательности компонентов / штрихов, из которых он состоит. Есть две проблемы:

  • Некоторые компоненты состоят из еще меньших компонентов , поэтому как разбить символ на «атомарные» компоненты не определяется однозначно. Если вы сделаете это до уровня отдельных ударов , вам понадобится характеристика каждого отдельного удара (позиция внутри символа, формы, направления и т. Д.). Я не думаю, что кто-либо, как каждый, сделал это (мне было бы очень интересно, если кто-нибудь скажет мне иначе).

  • Вам нужно будет поместить штрихи или компоненты в порядок . Очевидным кандидатом является канонический порядок штрихов персонажа, который описан в лексике, и есть даже словарные сайты с анимированными диаграммами порядка инсульта. Однако источники данных, которые я знаю (для японцев), генерируют эти анимации как последовательности растровой графики; Я никогда не видел человеческих или машиносчитываемых кодов, которые представляют последовательность штрихов (или даже имена отдельных штрихов) в форме, подходящей для вычисления расстояния редактирования.

Но последнее, что вы могли бы попробовать, это отобразить глифы символов и вычислить расстояние редактирования в зависимости от того, сколько пикселей (или векторов) необходимо изменить, чтобы превратить один символ в другой. Однажды я сделал это для латинских символов и комбинаций символов (на пиксельной основе) в контексте посткоррекции OCR, и результаты были весьма обнадеживающими.

Быстрый ответ на комментарий larsmans ниже: Существуют две связанные концепции, определенные стандартом Unicode (ниже я ссылаюсь на версию 6.0, глава 12 ):

  1. Индекс, основанный на количествах радикалов и инсульта. Каждый символ Хана состоит из нескольких компонентов, один из которых является радикалом. Индекс количества радикалов / штрихов - это список символов, отсортированный по радикалу (т.е. все символы, которые имеют один и тот же радикал, сгруппированные вместе), и каждая группа с радикальной категорией, внутренне отсортированная по количеству штрихов, используемых в остальной части персонажа. К сожалению, даже это не определено однозначно - есть символы, радикал которых определяется по-разному с помощью традиционной традиционной лексики, а также может быть сложным подсчет хода инсульта. Вот что говорит Unicode Standard:

    Чтобы ускорить поиск определенных хэно-идеографических символов в кодовых диаграммах, индексы радикальных штрихов предоставляются на веб-сайте Юникода. [...] Самым влиятельным авторитетом для информации о радикальных инсультах является словарь KangXi восемнадцатого века, который содержит 214 радикалов. Главная проблема использования радикалов KangXi сегодня заключается в том, что многие упрощенные символы трудно классифицировать под любым из радикалов K4XXi. В результате были введены различные современные радикальные наборы. Однако ни один из них не используется, и 214 радикалов KangXi остаются наиболее известными. [...] Радикальные диаграммы Unicode основаны на радикалах KangXi. Стандарт Unicode следует за несколькими различными источниками для классификации радикального удара. В тех случаях, когда два источника расходятся в отношении количества радикалов или инсульта для данного символа, символ отображается в обеих позициях в диаграммах радикальных штрихов.

    Обратите внимание, что даже если мы предположим, что индекс радикала / хода должен быть однозначным и правильным, он не будет достаточным источником информации для преобразования символа в последовательность компонентов, поскольку единственным компонентом персонажа, полностью описанным этим, является радикал.

  2. Последовательности Идеографического описания (раздел 12.2): Юникод определяет кодовые точки для основных компонентов символов (большинство из них сами по себе могут использоваться как автономные символы), и есть кодовые точки, используемые для склеивания их вместе, чтобы сформировать последовательность компонентов, которая описывает состав более сложного характера. Таким образом, это работает аналогично сочетанию символов , но есть важные отличия:

    1. Порядок компонентов не определяется однозначно
    2. Не существует определения механизма рендеринга для таких последовательностей
    3. Нет сопоставления от обычных символов к соответствующим последовательностям идеографического описания (хотя в Стандарте упоминается, что такие отображения в некоторой степени существуют в источниках, которые они использовали для компиляции набора символов Хан).

    Стандарт предполагает, что последовательности идеографического описания используются для описания сложных или редких характеристик, которые не представлены какой-либо существующей кодовой точкой; но он явно препятствует использованию последовательностей описания вместо обычных символов:

    В частности, последовательности Идеографического описания не должны использоваться для предоставления альтернативных графических изображений кодированных идеографов при обмене данными. Затем поиск, сортировка и другие текстовые операции на основе контента потерпят неудачу.

Мы разрабатываем систему для нечеткого сопоставления на более чем 50 международных языках с использованием стандартного символа Unicode UTF-8, UTF-16 и UTF-32. До сих пор мы могли использовать расстояние Левенштейна для обнаружения орфографических символов расширенных символов английского языка Unicode.

Мы хотели бы расширить эту систему для обработки китайских иероглифов, представленных в Юникоде. Как мы будем проводить расчет расстояния Левенштейна между похожими китайскими иероглифами?





edit-distance