Ограничения и альтернативы попыткам на языках, отличных от английского?

Структура данных trie часто является отличным способом хранения строк на английском языке. Он работает, создавая дерево, где каждое ребро помечено буквой, а путь к отмеченному node в дереве вызывает одно из слов в структуре данных.

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

Я являюсь носителем английского языка с ограниченным знанием других языков и алфавитов, но похоже, что многие из этих свойств не хранятся на других языках. Я знаю, что французский, испанский, немецкий и венгерский, например, часто используют символы с акцентом, которые не хранятся непрерывно с остальными буквами в пространстве Юникода. На иврите и на арабском языке обозначены гласные, которые обычно указаны выше или ниже каждой буквы. Китайцы используют систему логограмм, а символы корейского хангула состоят из тройки меньших символов, сгруппированных вместе.

Делают ли попытки все еще хорошо работать для данных, хранящихся на этих языках и алфавитах? Какие изменения, если таковые имеются, необходимы для использования попыток для такого рода данных? Существуют ли какие-либо структуры данных, которые хорошо работают для строк на этих языках и алфавитах, которые особенно хорошо подходят для них, но не будут полезны или эффективны на английском языке?

Ответы

Ответ 1

Как дополнение к ответу @JimMischel, я хотел бы затронуть проблему, что на других языках часто существует несколько эквивалентных способов написания одной и той же вещи. Vietnamese (на основе латинского/английского script) является особенно хорошим примером, когда буквы с двумя акцентами являются общими. Например, Ặ (U + 1EB6) можно технически также записать с последовательностями Ă + dot, Ạ + breve, A + breve + dot, A + dot + breve.

Нормализация Unicode может решить эту проблему, преобразовая строку в стандартизованный канонический порядок. Существует 4 различных варианта: NFC, NFKC, NFD и NFKD. Здесь я не буду вдаваться в подробности, но первые две являются "составленными формами", которые имеют тенденцию укорачивать строку, группируя базовые символы с ее акцентами, а последние два являются "разложенными формами", делая обратное.

Hangul - интересный случай: это алфавит, хотя все буквы слога записываются вместе в блок. В Юникоде существуют как отдельные буквы, так и слоговые блоки. Нормализация может решить эту проблему, хотя число отдельных слогов довольно велико. Использование NFC/NFKC может быть не полезно для trie, но в этом случае использование NFD/NFKD для разложения слогов на составляющие буквы будет работать.

Несколько других не связанных между собой точек зрения:

  • В дополнение к точке garconon/garcon, которая уже поднята, у вас есть проблема cote/coté/côte/côté, в которой есть все различные французские слова. Точно так же знаки гласных на иврите и на арабском языке обычно не являются обязательными, что может иногда вызывать неоднозначность.
  • Алфавиты 1 Южной и Юго-Восточной Азии могут стать большими по сравнению с английским, что примерно в два раза больше.
  • Они строго называются abugidas, где гласные записываются как диакритики/акценты, но это различие обычно можно игнорировать с точки зрения программирования.

Ответ 2

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

Последовательные значения Unicode английских символов на самом деле не являются огромным преимуществом. Хотя он предлагает простую реализацию node:

CharNode
    char
    array[26] of CharNode

Эта структура не особенно полезна. Это может сделать вещи быстрее, но при довольно высокой стоимости памяти. Даже на втором уровне три, этот массив необычайно редок. К тому времени, когда вы доберетесь до четвертого или пятого уровня, это почти все мертвое пространство. Я проанализировал это в какой-то момент. Я посмотрю вокруг и посмотрю, есть ли у меня все номера.

Я нашел почти столь же быстрым, чтобы иметь массив переменной длины в node, с элементами, упорядоченными по частоте. Помимо второго или третьего уровня три, персонаж, которого я искал, почти всегда находился в первой или второй позиции в этом массиве. И экономия пространства была довольно большой. Вместо 26 ссылок на node (104 байта в моей реализации) у меня было однобайтное количество, а затем пять байтов на ссылку. Таким образом, пока осталось менее 21 ребенка для определенного node (что было в большинстве случаев), я сохранил пространство. Был небольшой штраф за выполнение, но недостаточно, чтобы мое выражение касалось вопроса.

Это единственная модификация, которую я должен был внести в свою trie-структуру, чтобы она поддерживала все алфавитные языки, с которыми я работал. Как я уже сказал, я работал в основном с западноевропейскими языками, и для тех, с кем он работал красиво. Я знаю, что он работал с ивритом и арабским, но я не знаю, как хорошо это работает. Это соответствовало нашим целям, но было ли оно удовлетворено носителем языка неизвестно.

Trie, который я построил, работал достаточно хорошо для наших целей на любом языке, символы которого соответствуют базовому многоязычному языку Unicode. При работе с суррогатными парами было немного странно, но мы в значительной степени игнорировали их. В принципе, мы просто рассматривали суррогатную пару как два символа и позволяли этому идти.

Вам нужно решить, хотите ли вы обрабатывать акцентированные символы как отдельные символы, или если вы хотите их сопоставить. Рассмотрим, например, французское слово "garçon", которое некоторые люди произнесут "garcon", либо потому, что они не знают ничего лучше, либо не знают, как создать персонажа "ç". В зависимости от того, для чего вы используете trie for, вам может показаться полезным преобразовать символы с акцентом в их эквиваленты без акцента. Но я полагаю, что больше проблемы с очисткой ввода, чем проблема trie.

Что мой довольно длинный способ сказать, что стандартное правило должно хорошо работать для любого алфавитного языка без каких-либо изменений, специфичных для языка. Я не вижу никакого очевидного способа использовать trie для логографического языка. Я ничего не знаю о корейском хангуле, поэтому я не могу сказать, будет ли там полезно.