Структура данных по типу словаря T9

Ответ 1

Он может быть реализован несколькими способами, один из которых Trie. Маршрут представлен цифрами, а узлы указывают на сбор слов.

Он может быть реализован с использованием вложенных хеш-таблиц, ключ хеш-таблицы - это буква и на каждой цифре алгоритм вычисляет все возможные маршруты (маршруты O (3 ^ n)).

Ответ 2

4663

переводится на

{G, Н, I} {М, N, О} {М, N, О} {D, Е, F}

T9 работает, фильтруя возможности вниз последовательно, начиная с первых возможных букв. Итак, первым шагом в вашем примере будет фильтрация списка слов со всеми словами, начинающимися с G, H или I. Следующий шаг, возьмите этот список и отфильтруйте второй буквой M, N, O. И так далее...

Ответ 3

Я думаю, что T9 использует Trie на основе бит-карты. На первом уровне есть 32-битное (я предполагаю, что они были расширены до 32), где каждый бит представляет букву. Все буквы, которые являются действительными в качестве начальных букв для слова, имеют свой бит.

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

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

Ответ 4

Я предполагаю, что до тех пор, пока T9 не использует trie, где ссылки представлены растровым изображением (1 бит на букву). Это называется сжатой структурой данных, как объясняет Стив Ханов:

http://stevehanov.ca/blog/index.php?id=120

Ответ 5

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

Затем вам, вероятно, придется сортировать результирующие списки в некотором роде, поэтому более вероятные слова появляются перед менее вероятными словами (если у вас есть пространство, я бы также включил небольшую область для счетчика, поэтому мы можем пошаговое повторное сортирование этих ИЛИ просто mov ethe, используемых последним в списке предложений, поэтому мы со временем стремимся дать пользователю лучший ответ).

Таким образом, когда у вас есть 4663 в качестве входа, вы можете довольно просто получить соответствующий связанный список wit ha примерно O (1) поиск хеш-таблицы.

Ответ 6

Реализация С# с использованием Trie

        public interface ICellT9
        {
            void Add(string a_name);

            List<string> GetNames(string a_number);
        }

        public class Cell : ICellT9
        {
            private Dictionary<int, Cell> m_nodeHolder;
            private List<string> m_nameList;

            public Cell()
            {
                m_nameList = new List<string>();
                m_nodeHolder = new Dictionary<int, Cell>();

                for (int i = 2; i < 10; i++)
                {
                    m_nodeHolder.Add(i, null);
                }
            }

            public void Add(string a_name)
            {
                Add(a_name, a_name);
            }

            private void Add(string a_name, string a_originalName)
            {
                if (string.IsNullOrEmpty(a_name) && 
                   (string.IsNullOrEmpty(a_originalName) == false))
                {
                    m_nameList.Add(a_originalName);
                }
                else
                {
                    int l_firstNumber = CharToNumber(a_name[0].ToString());

                    if (m_nodeHolder[l_firstNumber] == null)
                    {
                        m_nodeHolder[l_firstNumber] = new Cell();
                    }

                    m_nodeHolder[l_firstNumber].Add(a_name.Remove(0, 1), a_originalName);
                }
            }

            public List<string> GetNames(string a_number)
            {
                List<string> l_result = null;

                if (string.IsNullOrEmpty(a_number))
                {
                    return l_result;
                }

                int l_firstNumber = a_number[0] - '0';

                if (a_number.Length == 1)
                {
                    l_result = m_nodeHolder[l_firstNumber].m_nameList;
                }
                else if(m_nodeHolder[l_firstNumber] != null)
                {
                    l_result = m_nodeHolder[l_firstNumber].GetNames(a_number.Remove(0, 1));
                }

                return l_result;

            }

            private int CharToNumber(string c)
            {
                int l_result = 0;

                if (c == "a" || c == "b" || c == "c")
                {
                    l_result = 2;
                }
                else if (c == "d" || c == "e" || c == "f")
                {
                    l_result = 3;
                }
                else if (c == "g" || c == "h" || c == "i")
                {
                    l_result = 4;
                }
                else if (c == "j" || c == "k" || c == "l")
                {
                    l_result = 5;
                }
                else if (c == "m" || c == "n" || c == "o")
                {
                    l_result = 6;
                }
                else if (c == "p" || c == "q" || c == "r" || c == "s")
                {
                    l_result = 7;
                }
                else if (c == "t" || c == "u" || c == "v")
                {
                    l_result = 8;
                }
                else if (c == "w" || c == "x" || c == "y" || c == "z")
                {
                    l_result = 9;
                }

                return l_result;
            }
        }