algorithm - swiftkey - teclado t9 android 2018
Estructura de datos detrás del tipo de diccionario T9 (6)
¿Cómo funciona un diccionario T9? ¿Cuál es la estructura de datos detrás de esto? Si tecleamos ''4663'' obtenemos ''bueno'' cuando presionamos el botón ''get gone'', luego ''home'', etc. ...
EDITAR: si el usuario ingresa 46, debe mostrar ''ir'' y cuando se presiona la flecha hacia abajo debe mostrar ''desaparecido'', etc.
4663
se traduce a
{G, H, I} {M, N, O} {M, N, O} {D, E, F}
T9 funciona 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 ...
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 luego 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.
Implementación de C # usando 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;
}
}
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, probablemente necesite ordenar las listas resultantes de alguna manera, por lo que aparecerán palabras más probables antes de palabras menos probables (si tiene espacio, también incluiría un área pequeña para un contador, de modo que podamos reajustar gradualmente clasifique estos o simplemente mov ethe utilizados por última vez al principio de la lista de sugerencias, para que, con el tiempo, tiendamos a darle al usuario una mejor respuesta).
De esta forma, cuando tiene 4663 como entrada, puede simplemente recuperar la lista enlazada relevante con aproximadamente O (1) búsqueda de tablas hash.
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.
También se puede implementar usando tablas hash anidadas, la clave de la tabla hash es una letra y en cada dígito el algoritmo calcula todas las rutas posibles (O (3 ^ n) rutas).
Supongo que, como los anteriores, T9 usa un trie, donde los enlaces están representados por un mapa de bits (1 bit por letra). Esto se llama una estructura de datos sucinta, como Steve Hanov explica muy bien: