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

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

      c
     / \
    a   i
     \ /
      t
      |
      e

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

Вопросы:

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

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


dictionary string data-structures finite-automata dawg
person Schemer    schedule 17.12.2014    source источник
comment
в DAWG-DAFSA символы являются ребрами, а не узлами.   -  person Jasen    schedule 02.07.2019

Ответы (1)


arrow_upward
3
arrow_downward

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

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

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

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

person templatetypedef    schedule 17.12.2014
comment
Определенно помогает. Большое спасибо. Статья в Википедии вообще не затрагивала проблемы ложных срабатываний/отрицательных результатов. Мои строки не ограничиваются английскими словами, поэтому я обеспокоен долгосрочными последствиями реализации trie без планирования какой-либо обрезки или другого обслуживания, что заставило меня задуматься о реализации некоторого сжатия. - person Schemer; 17.12.2014
comment
26 МБ может быть доступным, но, уменьшая объем памяти, мы также можем улучшить время поиска, потому что большая часть словаря может поместиться в кэши. - person Evgeni Sergeev; 25.11.2016