Struttura dati dietro il tipo di dizionario T9

Question

Come funziona un dizionario T9? Qual è la struttura dati dietro di esso. Se digitiamo '4663' otteniamo 'buono' quando premiamo il tasto otteniamo 'andato', poi 'casa' ecc ...

MODIFICA: Se l'utente digita 46, dovrebbe mostrare "vai" e quando premuto freccia giù dovrebbe mostrare 'andato' ecc ...

Answer 1

Può essere implementato in diversi modi, uno di questi è Trie. Il percorso è rappresentato dalle cifre e i nodi puntano alla raccolta di parole.

Può essere implementato utilizzando tabelle hash nidificate, la chiave di hash table è una lettera e su ogni cifra l'algoritmo calcola tutti i percorsi possibili (percorsi O (3^n)).

Answer 2

traduce

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

T9 funziona filtrando le possibilità in ordine sequenziale iniziando con le prime lettere possibili. Quindi il primo passo nel tuo esempio sarà quello di filtrare l'elenco dei dizionari a tutte le parole che iniziano con G, H o I. Passo successivo, prendi quell'elenco e filtra le seconde lettere per M, N, O. E così via ...

Answer 3

Penso che T9 stia usando un Trie basato su una mappa di bit. Al primo livello c'è una parola a 32 bit (presumo che abbia espanso a 32) dove ogni bit rappresenta una lettera. Tutte le lettere che sono valide come lettere iniziali per una parola hanno il loro bit impostato.

Nel livello successivo è presente una mappa a 32 bit per ciascuno di quei bit impostati nel livello precedente. In queste mappe ogni bit viene impostato se la lettera corrispondente è valida come seconda lettera in una parola, con la lettera iniziale decisa dal primo livello.

La struttura continua quindi. L'utilizzo di un bit per lettera rende lo storage molto efficiente. Lo schema di indirizzamento deve tuttavia essere impegnativo. Potrebbe anche esserci un qualche tipo di ottimizzazione usando lo schema precedente per le parole brevi mentre si usa qualcos'altro per parole più lunghe.

Answer 4

Probabilmente lo farei iniziando con un dizionario, quindi (per ogni parola) spingere la parola in una lista digitata dai numeri che potrebbero formare la parola.

Quindi, probabilmente dovrai ordinare gli elenchi risultanti in qualche modo, quindi le parole più probabili vengono visualizzate prima delle parole meno probabili (se hai lo spazio, includerei anche una piccola area per un contatore, quindi può riordinare in modo incrementale questi OR semplicemente spostando l'ultimo usato nella parte anteriore dell'elenco di suggerimenti, quindi, nel tempo, tendiamo a dare all'utente una risposta migliore).

In questo modo, quando si dispone di 4663 come input, è possibile semplicemente recuperare l'elenco collegato rilevante con circa O (1) ricerca tabella hash.

Answer 5

Suppongo, come quelli precedenti che T9 usi un trie, in cui i collegamenti sono rappresentati da una bitmap (1 bit per lettera). Questo si chiama una struttura di dati succinta, come Steve Hanov spiega molto bene:

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

Answer 6

C# implementazione utilizzando 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; 
      } 
     }