Мета-информация в DAWG/DAFSA

Question

Я хотел бы реализовать структуру данных для поиска строк, для динамических строк, которая будет поддерживать эффективный поиск и вставку. В настоящее время я использую три, но я хотел бы уменьшить объем памяти, если это возможно. В этой статье в Википедии описывается DAWG/DAFSA, которая, очевидно, сэкономит много места на дереве путем сжатия суффиксов. Однако, хотя он будет четко проверять, является ли строка допустимой, для меня не очевидно, есть ли способ исключить недопустимые строки. Например, используя слова "cite" и "cat", где "t" и "e" являются терминальными состояниями, DAWG / DAFSA будет выглядеть следующим образом:

      c
     / \
    a   i
     \ /
      t
      |
      e

и "cit" и "cate" будут неправильно распознаваться как допустимые строки без некоторой мета-информации.

Вопросы:

1) Есть ли предпочтительный способ хранения метаинформации о строках / путях (например, легальности) в DAWG / DAFSA?

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

Answer 1

В DAWG вы сжимаете состояния только вместе, если они абсолютно неотличимы друг от друга. Это означает, что вы на самом деле не будете объединять T-узлы для CAT и CITE по той причине, которую вы указали - это дает вам либо ложный положительный результат на CIT, либо ложный отрицательный на CAT.

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

Честно говоря, для наборов данных разумного размера это неплохой вызов. Trie для всего английского будет использовать только что-то вроде 26 МБ, что не очень много. Я бы пошел с DAWG только в том случае, если использование пространства действительно дорого, а вы не делаете много вставок или удалений.

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