В этой минимальной идеальной хеширующей функции, что подразумевается под FirstLetter и Предшественником?

Question

Я реализую Minimalistic Acyclic Finite State Automaton (MA-FSA, определенный тип DAG) в Go и хотел бы связать некоторые дополнительные данные с узлами, которые указывают EOW (конец слова). С MA-FSA традиционный подход невозможен, поскольку на этом узле может быть несколько слов. Поэтому я рассматриваю минимальные совершенные хэширующие функции в качестве альтернативы.

В поле «Коррекция» в верхней части his blog post, Steve Hanov указано, что он использовал метод, описанный в this paper by Lucchesi and Kowaltowski. При взгляде на Рисунок 12 (стр. 19) описывает функцию хэширования.

В строке 8 он относится к FirstLetter и Predecessor(), но он не описывает, что они собой представляют. Или я этого не вижу. Кто они такие?

Все, что я могу понять, это то, что он просто пересекает дерево, добавляя Number от каждого узла, когда он идет, но это, возможно, не так. Он создает слишком большие числа, и это не одно к одному, как говорится в документе. Я что-то неправильно понял?

Answer 1

В документе говорится:

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

Так что я считаю, что это: for C <- FirstLetter to Predecessor(Word[I ]) do

Средства: for (c = 'a'; c < word[i]; c++)

(Они просто пытаются быть алфавит независимым.)

Подумайте об этом так: перечислить все принятые слова , Сортируйте их. Найдите свое слово в списке. Его индекс - это хеш-значение слова.

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

Answer 2

Я обновил свой пример DAWG, чтобы показать его как карту от ключей до значений. Каждый узел хранит количество конечных узлов, доступных из него (включая себя). Затем, когда trie пройден, мы добавляем подсчеты любого, что мы пропускаем. Таким образом, каждое слово в trie имеет уникальный номер. Затем вы можете найти число в массиве, чтобы получить данные, связанные со словом.

https://gist.github.com/smhanov/94230b422c2100ae4218