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

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


c++ data-structures dawg
person Usman Amjed    schedule 24.12.2012    source источник

Ответы (3)


arrow_upward
2
arrow_downward

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

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

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

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

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

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

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

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

person templatetypedef    schedule 24.12.2012
comment
Какую структуру данных вы бы предложили? Должен ли я пойти на попытку? Люди говорят об использовании памяти в трее? Но не мог бы я построить три, а затем сохранить его; не строить его снова и снова. Кроме того, проблема с памятью настолько велика? - person Usman Amjed; 25.12.2012
comment
В онлайн-справочнике предлагается использовать этот метод для DAWG: поскольку конечные узлы DAWG могут быть доступны по нескольким путям, DAWG не может напрямую хранить вспомогательную информацию, относящуюся к каждому пути, например. частотность слова в английском языке. Однако, если в каждом узле мы храним подсчет количества уникальных путей через структуру из этой точки, мы можем использовать его для получения индекса слова или слова с заданным индексом.[1] Затем вспомогательная информация может быть сохранена в массиве. - person Usman Amjed; 25.12.2012

arrow_upward
2
arrow_downward

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

person John with waffle    schedule 24.12.2012
comment
Вы можете остановиться на этом? Я думаю, что это немного более тонко, чем вы думаете. Вы не можете обязательно хранить информацию для каждого узла или ребра для слова уникальным образом, потому что, если бы вы это сделали, вы могли бы случайно иметь несколько разных слов, разделяющих эту информацию. Если бы вы вместо этого хранили всю информацию для каждого узла или для каждого пути отдельно, вы фактически расширили DAWG до дерева, полностью устранив прирост эффективности. - person templatetypedef; 25.12.2012
comment
^^ У меня тот же вопрос. Можете ли вы привести пример? - person Usman Amjed; 25.12.2012
comment
Справедливости ради, я ответил на вопрос буквально: можно ли аннотировать пути в ориентированном взвешенном ациклическом графе. Да, можно. Можно ли эффективно аннотировать пути в ориентированном взвешенном ациклическом графе, особенно по сравнению с этой другой реализацией? Скорее всего нет. В целом, было бы неплохо расширить вопрос, чтобы дать другим больше информации о намерениях. - person John with waffle; 04.01.2013

arrow_upward
0
arrow_downward

Да, ты можешь. Каждый путь от начала dawg до конца слова уникален, и этот путь можно индексировать как целое число. Затем этот номер индекса может быть сопоставлен со вспомогательной информацией.

См. статью здесь: http://www.ic.unicamp.br/~reltech/1992/92-01.pdf См. хорошую реализацию здесь: https://github.com/WojciechMula/pyDAWG/blob/master/dawg_mph.c#L37

person rossb83    schedule 08.12.2017