algorithm - tipos - valor bases de datos

Cómo buscar rápidamente una colección de clave/valor basada en cadena

Question

¡Hola compañeros stackoverflowers!

Tengo una lista de palabras de 200,000 entradas de cadenas, la longitud promedio de las cadenas es de alrededor de 30 caracteres. Esta lista de palabras es la clave y para cada tecla tengo un objeto de dominio. Me gustaría encontrar los objetos de dominio en esta colección solo conociendo una parte de la clave. Es decir, la cadena de búsqueda "kov" coincidiría, por ejemplo, con la clave "stackoverflow".

Actualmente estoy usando un árbol de búsqueda ternaria (TST), que generalmente encontrará los artículos dentro de 100 milisegundos. Sin embargo, esto es demasiado lento para mis requerimientos. La implementación de TST podría mejorarse con algunas optimizaciones menores y podría intentar equilibrar el árbol. Pero pensé que estas cosas no me darían la mejora de velocidad 5x - 10x a la que aspiro. Asumo que la razón de ser tan lenta es que básicamente tengo que visitar la mayoría de los nodos en el árbol.

¿Alguna idea sobre cómo mejorar la velocidad del algoritmo? ¿Hay algún otro algoritmo que debería estar mirando?

Gracias de antemano, Oskar

Answer 1

Suffix Array y q -gram index

Si sus cadenas tienen un límite superior estricto en el tamaño, puede considerar el uso de una matriz de sufijos : simplemente agregue todas las cadenas a la misma longitud máxima utilizando un carácter especial (por ejemplo, el carácter nulo). A continuación, concatene todas las cadenas y cree un índice de matriz de sufijos sobre ellas.

Esto le da un tiempo de ejecución de búsqueda de m * log n donde m es la longitud de su cadena de consulta yn es la longitud total de las cadenas combinadas. Si esto todavía no es lo suficientemente bueno y su m tiene una longitud fija, pequeña, y su alfabeto Σ tiene un tamaño restringido (digamos, Σ <128 caracteres diferentes), puede además generar un índice de q -gramos . Esto permitirá la recuperación en tiempo constante . Sin embargo, la tabla q -gram requiere Σm entradas (= 8 MiB en el caso de solo 3 caracteres, y 1 GiB para 4 caracteres!).

Hacer el índice más pequeño

Podría ser posible reducir el tamaño de la tabla q -gram (exponencialmente, en el mejor de los casos) ajustando la función hash. En lugar de asignar un número único a cada qgrama posible, puede emplear una función hash con pérdida. La tabla tendría que almacenar listas de posibles índices de matriz de sufijos en lugar de solo una entrada de matriz de sufijos correspondiente a una coincidencia exacta. Esto implicaría que la búsqueda ya no es constante, porque todas las entradas en la lista tendrían que ser consideradas.

Por cierto, no estoy seguro de si está familiarizado con cómo funciona un índice de q -gram, ya que Internet no es útil en este tema. Ya he mencionado esto en otro tema. Por lo tanto, he incluido una descripción y un algoritmo para la construcción en mi tesis de licenciatura .

Prueba de concepto

He escrito una prueba de concepto muy pequeña de C # (ya que de otra manera usted indicó que trabajó con C #). Funciona, sin embargo, es muy lento por dos razones. Primero, la creación del conjunto de sufijos simplemente ordena los sufijos. Esto solo tiene tiempo de ejecución n ² log n . Hay métodos muy superiores. Peor aún, sin embargo, es el hecho de que uso SubString para obtener los sufijos. Desafortunadamente, .NET crea copias del sufijo completo para esto. Para utilizar este código en la práctica, asegúrese de utilizar métodos in situ que no copien innecesariamente datos. Lo mismo es cierto para recuperar los q -gramas de la cadena.

Posiblemente sería mejor no construir la cadena m_Data utilizada en mi ejemplo. En su lugar, podría guardar una referencia a la matriz original y simular todos mis accesos SubString trabajando en esta matriz.

Aún así, es fácil ver que esta implementación esencialmente ha esperado una recuperación de tiempo constante (¡si el diccionario se comporta bien)! ¡Este es un gran logro que no puede ser superado por un árbol de búsqueda / trie!

class QGramIndex {
private readonly int m_Maxlen;
private readonly string m_Data;
private readonly int m_Q;
private int[] m_SA;
private Dictionary<string, int> m_Dir = new Dictionary<string, int>();
private struct StrCmp : IComparer<int> {
public readonly String Data;
public StrCmp(string data) { Data = data; }
public int Compare(int x, int y) {
return string.CompareOrdinal(Data.Substring(x), Data.Substring(y));
}
}
private readonly StrCmp cmp;
public QGramIndex(IList<string> strings, int maxlen, int q) {
m_Maxlen = maxlen;
m_Q = q;
var sb = new StringBuilder(strings.Count * maxlen);
foreach (string str in strings)
sb.AppendFormat(str.PadRight(maxlen, ''/u0000''));
m_Data = sb.ToString();
cmp = new StrCmp(m_Data);
MakeSuffixArray();
MakeIndex();
}
public int this[string s] { get { return FindInIndex(s); } }
private void MakeSuffixArray() {
// Approx. runtime: n^3 * log n!!!
// But I claim the shortest ever implementation of a suffix array!
m_SA = Enumerable.Range(0, m_Data.Length).ToArray();
Array.Sort(m_SA, cmp);
}
private int FindInArray(int ith) {
return Array.BinarySearch(m_SA, ith, cmp);
}
private int FindInIndex(string s) {
int idx;
if (!m_Dir.TryGetValue(s, out idx))
return -1;
return m_SA[idx] / m_Maxlen;
}
private string QGram(int i) {
return i > m_Data.Length - m_Q ?
m_Data.Substring(i) :
m_Data.Substring(i, m_Q);
}
private void MakeIndex() {
for (int i = 0; i < m_Data.Length; ++i) {
int pos = FindInArray(i);
if (pos < 0) continue;
m_Dir[QGram(i)] = pos;
}
}
}

Ejemplo de uso:

static void Main(string[] args) {
var strings = new [] { "hello", "world", "this", "is", "a",
"funny", "test", "which", "i", "have",
"taken", "much", "too", "far", "already" };
var index = new QGramIndex(strings, 10, 3);
var tests = new [] { "xyz", "aki", "ake", "muc", "uch", "too", "fun", "est",
"hic", "ell", "llo", "his" };
foreach (var str in tests) {
int pos = index[str];
if (pos > -1)
Console.WriteLine("/"{0}/" found in /"{1}/".", str, strings[pos]);
else
Console.WriteLine("/"{0}/" not found.", str);
}
}

Answer 2

¿Sería posible "hash" el valor clave? Básicamente, un segundo árbol mostrará todos los valores posibles para buscar una lista de llaves en el primer árbol.

Vas a necesitar 2 árboles; El primero es un valor hash para el objeto de dominio. el segundo árbol es las cadenas de búsqueda para el valor hash. el segundo árbol tiene varias claves para el mismo valor hash.

Árbol de ejemplo 1: STCKVRFLW -> objeto de dominio

árbol 2: pila -> STCKVRFLW, STCK sobre -> STCKVRFLW, VRBRD, VR

Entonces, al buscar en el 2 ° árbol, se obtiene una lista de las claves para buscar en el 1er árbol.

Answer 3

¿Tendría alguna ventaja con sus llaves comparables al tamaño del registro de la máquina? Entonces, si estás en un cuadro de 32 bits, puedes comparar 4 caracteres a la vez en lugar de cada personaje individualmente. No sé qué tan malo aumentaría el tamaño de tu aplicación.

Answer 4

Aquí hay un WAG para ti. No estoy de ninguna manera Knuthian en mi algoritmo experto

De acuerdo, entonces el ingenuo Trie codifica las llaves de cadena comenzando en la raíz del árbol y moviéndose hacia abajo por las ramas que coinciden con cada letra de la tecla, comenzando por la primera letra de la tecla. Entonces, la clave "foo" se correlacionaría con (root)->f->fo->foo y el valor se almacenaría en la ubicación apuntada por el nodo ''foo''.

Está buscando CUALQUIER subcadena dentro de la clave, no solo subcadenas que comienzan al principio de la clave.

Entonces, lo que necesita hacer es asociar un nodo con CUALQUIER tecla que contenga esa subcadena particular. En el ejemplo de foo que di antes, NO habrías encontrado una referencia al valor de foo bajo los nodos ''f'' y ''fo''. En un TST que admite el tipo de búsqueda que está buscando hacer, no solo encontrará el objeto foo en los tres nodos (''f'', ''fo'' y ''foo''), también lo encontrará. debajo de ''o'' y ''oo'' también.

Hay un par de consecuencias obvias para expandir el árbol de búsqueda para admitir este tipo de indexación. Primero, acabas de explotar el tamaño del árbol. Asombrosamente. Si puede almacenarlo y usarlo de manera eficiente, sus búsquedas tomarán O (1) vez. Si sus llaves permanecen estáticas, y puede encontrar una manera de dividir el índice para que no se aplique una gran penalización de E / S al usarlo, esto puede amortizarse para que valga la pena.

En segundo lugar, descubrirá que las búsquedas de cadenas pequeñas darán como resultado números masivos de visitas, lo que puede hacer que su búsqueda sea inútil a menos que, por ejemplo, ponga una longitud mínima en los términos de búsqueda.

En el lado bueno, también puede encontrar que puede comprimir el árbol mediante tokenización (como lo hace la compresión de zip) o comprimiendo nodos que no se ramifican (es decir, si tiene ''w'' -> ''o'' -> '' o ''-> y la primera'' o ''no se bifurca, puede colapsarla de forma segura a'' w ''->'' oo ''). Tal vez incluso un hash de culo perverso podría facilitar las cosas ...

De todos modos, WAG como dije.

Answer 5

Elija un tamaño de cadena de búsqueda mínimo (por ejemplo, cuatro caracteres). Repase su lista de entradas de cadenas y cree un diccionario de cada subcadena de cuatro caracteres, asignando a una lista de entradas en la que aparece la subcadena. Cuando realice una búsqueda, busque los primeros cuatro caracteres de la cadena de búsqueda para buscar un conjunto inicial, luego limite ese conjunto inicial solo a aquellos que coinciden con la cadena de búsqueda completa.

El peor caso de esto es O (n), pero solo lo obtendrás si tus entradas de cadena son casi todas idénticas. Es probable que el diccionario de búsqueda sea bastante grande, por lo que probablemente sea una buena idea almacenarlo en un disco o usar una base de datos relacional :-)

Answer 6

/ EDITAR: Un amigo mío acaba de señalar una suposición estúpida en mi construcción de la tabla de q-gram. La construcción puede hacerse mucho más simple y, en consecuencia, mucho más rápida. He editado el código fuente y la explicación para reflejar esto. Creo que podría ser la solución final .

Inspirado por el comentario de Rafał Dowgird a mi respuesta anterior, he actualizado mi código. Creo que esto merece una respuesta propia, sin embargo, ya que también es bastante larga. En lugar de rellenar las cadenas existentes, este código crea el índice sobre la matriz original de cadenas. En lugar de almacenar una sola posición, la matriz de sufijos almacena un par: el índice de la cadena objetivo y la posición del sufijo en esa cadena. En el resultado, solo se necesita el primer número. Sin embargo, el segundo número es necesario para la construcción de la tabla q -gram.

La nueva versión del algoritmo construye la tabla de q- gramas caminando sobre la matriz de sufijos en lugar de las cadenas originales. Esto guarda la búsqueda binaria de la matriz de sufijos. En consecuencia, el tiempo de ejecución de la construcción cae desde O ( n * log n ) hasta O ( n ) (donde n es el tamaño de la matriz de sufijos).

Tenga en cuenta que, al igual que mi primera solución, el uso de SubString da SubString resultado muchas copias innecesarias. La solución obvia es escribir un método de extensión que cree un contenedor ligero en lugar de copiar la cadena. La comparación tiene que ser ligeramente adaptada. Esto se deja como un ejercicio para el lector. ;-)

using Position = System.Collections.Generic.KeyValuePair<int, int>;
class QGramIndex {
private readonly int m_Q;
private readonly IList<string> m_Data;
private Position[] m_SA;
private Dictionary<string, int> m_Dir;
public QGramIndex(IList<string> strings, int q) {
m_Q = q;
m_Data = strings;
MakeSuffixArray();
MakeIndex();
}
public int this[string s] { get { return FindInIndex(s); } }
private int FindInIndex(string s) {
int idx;
if (!m_Dir.TryGetValue(s, out idx))
return -1;
return m_SA[idx].Key;
}
private void MakeSuffixArray() {
int size = m_Data.Sum(str => str.Length < m_Q ? 0 : str.Length - m_Q + 1);
m_SA = new Position[size];
int pos = 0;
for (int i = 0; i < m_Data.Count; ++i)
for (int j = 0; j <= m_Data[i].Length - m_Q; ++j)
m_SA[pos++] = new Position(i, j);
Array.Sort(
m_SA,
(x, y) => string.CompareOrdinal(
m_Data[x.Key].Substring(x.Value),
m_Data[y.Key].Substring(y.Value)
)
);
}
private void MakeIndex() {
m_Dir = new Dictionary<string, int>(m_SA.Length);
// Every q-gram is a prefix in the suffix table.
for (int i = 0; i < m_SA.Length; ++i) {
var pos = m_SA[i];
m_Dir[m_Data[pos.Key].Substring(pos.Value, 5)] = i;
}
}
}

El uso es el mismo que en el otro ejemplo, menos el argumento maxlen requerido para el constructor.

Answer 7

Para consultar un conjunto grande de texto de manera eficiente, puede utilizar el concepto Editar distancia de distancia de edición de prefijo.

Editar distancia ED (x, y): cantidad mínima de transfroms para llegar de xa y

Pero calcular ED entre cada término y texto de consulta consume recursos y consume mucho tiempo. Por lo tanto, en lugar de calcular ED para cada término primero, podemos extraer posibles términos coincidentes utilizando una técnica denominada Índice Qgram . y luego aplica el cálculo ED en esos términos seleccionados.

Una ventaja de la técnica de índice de Qgram es que es compatible con la búsqueda difusa .

Un posible enfoque para adaptar el índice QGram es construir un índice invertido usando Qgrams. Allí almacenamos todas las palabras que constan de Qgram particular (en lugar de almacenar una cadena completa puede usar una ID única para cada cadena).

col: col mbia, col ombo, gan col a, ta col ama

Luego, al consultar, calculamos el número de Qgrams comunes entre el texto de la consulta y los términos disponibles.

Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4

Para los términos con un alto número de Qgramos comunes, calculamos el ED / PED contra el término de la consulta y luego sugerimos el término al usuario final.

puedes encontrar una implementación de esta teoría en el siguiente proyecto. No dude en hacer cualquier pregunta. https://github.com/Bhashitha-Gamage/City_Search

Para estudiar más sobre Editar distancia, Prefijo Editar índice de Qgram de distancia, mira el siguiente video del Prof. Dr. Hannah Bast https://www.youtube.com/embed/6pUg2wmGJRo (La lección comienza a partir de las 20:06)