Тройное дерево поиска со всеми предложениями автозаполнения в C # - PullRequest
Новая
       32

Тройное дерево поиска со всеми предложениями автозаполнения в C #

0 голосов
/ 21 ноября 2011

Интересно, можно ли изменить троичное дерево поиска, чтобы проверить, что слово существует И найти все слова, которые начинаются с этого слова (или заканчиваются этим словом?)?Например, do => dog dogs и т. Д.

С этого сайта приведен пример кода.Сначала загрузите все слова в троичное дерево, затем мы сможем использовать метод, чтобы проверить, существует ли слово. 

public class TernaryTree
{
    private Node m_root = null;

    private void Add(string s, int pos, ref Node node)
    {
        if (node == null) { node = new Node(s[pos], false); }

        if (s[pos] < node.m_char) { Add(s, pos, ref node.m_left); }
        else if (s[pos] > node.m_char) { Add(s, pos, ref node.m_right); }
        else
        {
            if (pos + 1 == s.Length) { node.m_wordEnd = true; }
            else { Add(s, pos + 1, ref node.m_center); }
        }
    }

    public void Add(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        Add(s, 0, ref m_root);
    }

    public bool Contains(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        int pos = 0;
        Node node = m_root;
        while (node != null)
        {
            int cmp = s[pos] - node.m_char;
            if (s[pos] < node.m_char) { node = node.m_left; }
            else if (s[pos] > node.m_char) { node = node.m_right; }
            else
            {
                if (++pos == s.Length) return node.m_wordEnd;
                node = node.m_center;
            }
        }

        return false;
    }
}

class Node
{
    internal char m_char;
    internal Node m_left, m_center, m_right;
    internal bool m_wordEnd;

    public Node(char ch, bool wordEnd)
    {
        m_char = ch;
        m_wordEnd = wordEnd;
    }
}

Это заставляет меня задуматься :(Любой способ получить эти слова может быть чем угодно.Однако я слаб в алгоритмах с этим уровнем ..Я надеюсь, что я не дублирую любые вопросы по этому поводу.Любое предложение, за которое я буду признателен.

1 Ответ

1 голос
/ 25 января 2012

Для этого можно использовать троичное дерево, но я бы не советовал (это нелегко сделать).

Я думаю, что вы можете использовать два разных подхода:

A., Используйте стандартное Trie вместо троичного дерева, поэтому время поиска будет считаться постоянным, независимо от того, сколько предметов у вас есть в Trie. Реализация на C # достижима, но имейте в виду, что Три требует среднего / высокого уровня знаний алгоритма.

B., Использовать стандартный отсортированный массив (строка []). Поскольку ваше требование состоит в том, чтобы просто создать автозаполнение на основе префикса, сохраните все ваши слова в строке [] и начните двоичный поиск для этого. Время поиска не является постоянным, а логарифмическим, но даже если в этом массиве хранятся миллионы слов, каждый поиск может быть измерен за доли миллисекунды (например, если в этом массиве миллион слов, всего 20 операций необходимо найти тот, который вы ищете). Даже если бинарный поиск не был успешным, у вас будет индекс, который является наиболее близким совпадением (но индекс будет отрицательным значением, указывая, что совпадение не было успешным). Итак, в этом массиве: 

A 
C
D 
E

если вы ищете B, вы получите индекс 0, указывающий на A. Если вы начнете повышаться, вы увидите элементы после «B» (или «собака» в вашем примере).

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

...