Estructura de datos detrás del tipo de diccionario T9

Question

¿Cómo funciona un diccionario T9? ¿Cuál es la estructura de datos detrás de esto? Si escribimos '4663' obtenemos 'bueno' cuando presionamos el botón obtenemos 'ido', luego 'home' etc. ...

EDITAR: Si el usuario escribe 46, entonces debería mostrar 'ir' y cuándo la flecha presionada hacia abajo debería mostrar 'desaparecido', etc.

Answer 1

Se puede implementar de varias maneras, una de ellas es Trie. La ruta está representada por los dígitos y los nodos apuntan a la colección de palabras.

Se puede implementar el uso de tablas resumen anidadas, así, la clave de la hash table es una carta y en todos los dígitos del algoritmo calcula todas las rutas posibles (O (n) 3^rutas).

Answer 2

traduce en

{G, H, I} {M, N, O} {M, N, O} {D, E, F}

T9 funciona por filtrando las posibilidades hacia abajo secuencialmente comenzando con las primeras letras posibles. Entonces, el primer paso en su ejemplo será filtrar la lista del diccionario a todas las palabras que comiencen con G, H o I. Luego, tome esa lista y filtre las segundas letras por M, N, O. Y así sucesivamente ...

Answer 3

Creo que T9 está utilizando un Trie basado en mapas de bits. En el primer nivel hay una palabra de 32 bits (supongo que se expandieron a 32) donde cada bit representa una letra. Todas las letras que son válidas como letras de inicio para una palabra tienen su bit establecido.

En el siguiente nivel hay un mapa de 32 bits para cada uno de esos bits que se establecieron en el nivel anterior. En estos mapas, cada bit se establece si la letra correspondiente es válida como una segunda letra en una palabra, con la letra de inicio decidida por el primer nivel.

La estructura continúa. Usar un bit por letra hace un almacenamiento muy eficiente. Sin embargo, el esquema de direccionamiento debe ser desafiante. También podría haber algún tipo de optimización utilizando el esquema anterior para palabras cortas mientras usa algo más para palabras más largas.

Answer 4

Probablemente lo haría comenzando con un diccionario, luego (para cada palabra) inserte la palabra en una lista marcada por los números que podrían formar la palabra.

Entonces, es probable que necesite para ordenar las listas resultantes de alguna manera, por lo que es más probable palabras aparecen antes que las palabras menos probable (si usted tiene el espacio, también me incluir un área pequeña para un contador, por lo que puede reordenar incrementalmente estos O simplemente mover el último usado al principio de la lista de sugerencias, para que, con el tiempo, tiendamos a darle al usuario una mejor respuesta).

esta manera, cuando usted tiene 4663 como una entrada, puede simplemente recuperar la lista relevante ingenio ligado HÅ más o menos O (1) tabla hash de búsqueda.

Answer 5

Supongo que, como los anteriores T9 utiliza un trie, donde los enlaces están representados por un mapa de bits (1 bit por letra). Esto se conoce como una estructura de datos sucinta, como Steve Hanov explica muy bien:

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

Answer 6

C# aplicación utilizando 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; 
      } 
     }