Можно ли использовать DAWG для хранения информации, связанной со словами?

Как правило, вы не можете хранить информацию по каждому слову в DAWG так же, как в дереве или другой структуре данных. Причина этого в том, что несколько разных слов в DAWG могут совместно использовать узлы, поэтому существует риск, что информация для одного слова «просочится» в информацию для других слов.

В качестве простого примера предположим, что у нас есть DAWG для слов «is», «as», «i» и «a». В этом случае DAWG будет выглядеть так:

                     START
a /     \ i
ACC    ACC
s  \     / s
ACC

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

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

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

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

Надеюсь это поможет!