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

Question

Как работает словарь T9? Какова структура данных за этим. Если мы набираем '4663', мы получаем 'хорошо', когда мы нажимаем кнопку, мы получаем 'ушел', затем 'домой' и т. Д ...

РЕДАКТИРОВАТЬ: если пользователь вводит 46, то он должен показывать «идти», а при нажатии стрелка вниз должен показывать «ушел» и т. Д.

Answer 1

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

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

Answer 2

4663

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

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

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

C # реализация с использованием 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;
            }
        }

Answer 6

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

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

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