Вопрос о внедрении Double Array Trie на github - PullRequest
Новая
       11

Вопрос о внедрении Double Array Trie на github

0 голосов
/ 18 декабря 2018

Я изучаю проект о Double Array Trie на GitHub. ссылка на GitHub .У меня есть некоторые проблемы с AhoCorasickDoubleArrayTrie.java. 

    private int insert(List<Map.Entry<Integer, State>> siblings)
    {
        int begin = 0;
        int pos = Math.max(siblings.get(0).getKey() + 1, nextCheckPos) - 1;
        int nonzero_num = 0;
        int first = 0;

        if (allocSize <= pos)
            resize(pos + 1);

        outer:
        while (true)
        {
            pos++;

            if (allocSize <= pos)
                resize(pos + 1);

            if (check[pos] != 0)
            {
                nonzero_num++;
                continue;
            }
            else if (first == 0)
            {
                nextCheckPos = pos;
                first = 1;
            }

            begin = pos - siblings.get(0).getKey(); 
            if (allocSize <= (begin + siblings.get(siblings.size() - 1).getKey()))
            {
                // progress can be zero 
                double l = (1.05 > 1.0 * keySize / (progress + 1)) ? 1.05 : 1.0 * keySize / (progress + 1);
                resize((int) (allocSize * l));
            }

            if (used[begin])
                continue;

            for (int i = 1; i < siblings.size(); i++)
                if (check[begin + siblings.get(i).getKey()] != 0)
                    continue outer;

            break;
        }

        if (1.0 * nonzero_num / (pos - nextCheckPos + 1) >= 0.95)
            nextCheckPos = pos;

        used[begin] = true;

        size = (size > begin + siblings.get(siblings.size() - 1).getKey() + 1) ? size : begin + siblings.get(siblings.size() - 1).getKey() + 1;

        for (Map.Entry<Integer, State> sibling : siblings)
        {
            check[begin + sibling.getKey()] = begin;
        }

        for (Map.Entry<Integer, State> sibling : siblings)
        {
            List<Map.Entry<Integer, State>> new_siblings = new ArrayList<Map.Entry<Integer, State>>(sibling.getValue().getSuccess().entrySet().size() + 1);

            if (fetch(sibling.getValue(), new_siblings) == 0)
            {
                base[begin + sibling.getKey()] = (-sibling.getValue().getLargestValueId() - 1);
                progress++;
            }
            else
            {
                int h = insert(new_siblings);   // dfs
                base[begin + sibling.getKey()] = h;
            }
            sibling.getValue().setIndex(begin + sibling.getKey());
        }
        return begin;
    }

в методе выборки, есть оператор if isAcceptable (), который проверяет, является ли узел терминальным узлом или нет,если узел является терминальным узлом, new_siblings вставит новый поддельный узел.и, наконец, вернуть размер new_siblings.

Я думаю, что, если узел не является терминальным узлом, у него должен быть дочерний узел, и дочерний узел будет добавлен в new_siblings.если узел является терминальным узлом, к нему будет добавлен поддельный узел.Таким образом, возвращаемое значение метода выборки не может быть равно нулю в обоих условиях.

, но в конце метода вставки оператор if (fetch (sibling.getValue (), new_siblings) == 0) "проверит, равно ли это возвращаемое значение нулю.Это не должно происходить в любое время.Я так растерялся, и я не знаю, что такое использование fakeNode.Пожалуйста, ведите меня, спасибо!

...