Ciertamente has visto las búsquedas de texto difuso en todas partes. Por ejemplo, escribe "stck" pero en realidad quiere decir "stack". ¿Alguna vez se preguntó cómo funciona esto?
Hay muchos algoritmos para hacer coincidencias de texto difuso, cada uno con sus propios pro y contras. Los más famosos son editar distancia y qgram. Quiero centrarme en qgrams hoy e implementar una muestra.
Básicamente qgrams son el algoritmo de coincidencia de cadenas difusas más adecuado para las bases de datos relacionales. Es bastante simple. "q" en qgram será reemplazado por un número como 2-gramo o 3-gramo o incluso 4-gramo.
2-gramo significa que cada palabra se divide en un conjunto de dos gramos de caracteres. "Pila" se dividirá en un conjunto de {"st", "ta", "ac", "ck"} o "base de datos" se dividirá en {"da", "at", "ta", "ba "," como "," se "}.
Una vez que las palabras se dividen en 2 gramos, podemos buscar en la base de datos un conjunto de valores en lugar de una cadena. Por ejemplo, si el usuario escribió mal "stck", cualquier búsqueda de "stck" no coincidirá con "stack" porque falta "a", pero el conjunto de 2 gramos {"st", "tc", "ck"} tiene 2 filas en común con el conjunto de 2 gramos de pila! Bingo encontramos una coincidencia muy cercana. No tiene nada en común con el conjunto de 2 gramos de la base de datos y solo 1 en común con el conjunto de 2 gramos de "stat", por lo que podemos sugerir fácilmente al usuario que quería escribir: primero "apilar" o segundo, "estrella" ".
Ahora impleméntelo con el servidor Sql: asuma un conjunto de datos de palabras hipotéticas. Necesita tener una relación de muchos a muchos entre 2 gramos y palabras.
CREATE TABLE Grams(twog char(2), wordId int, PRIMARY KEY (twog, wordId))
La tabla de gramos se debe agrupar en el primer botón y luego en la palabra Id para ver el rendimiento. Cuando consulta una palabra (por ejemplo, pila) coloca los gramos en una tabla temporal. Primero permitamos crear algunos millones de registros falsos.
--make millions of 2grams
DECLARE @i int =0
WHILE (@i<5000000)
BEGIN
-- a random 2gram
declare @rnum1 char = CHAR(CAST(RAND()*28 AS INT)+97)
declare @rnum2 char = CHAR(CAST(RAND()*28 AS INT)+97)
INS... INTO Grams (twog, wordId) VALUES (@rnum1 + @rnum2, CAST(RAND()*100000 AS int))
END
Ahora vamos a consulta la palabra "pila", que se romperá a: { 'st', 'ta', 'ac', 'ck'} dos gramos.
DECLARE @word TABLE(twog char(2)) -- 'stack'
INS... INTO @word VALUES ('st'), ('ta'), ('ac'), ('ck')
select wordId, count(*) from @word w inner join Grams g ON w.twog = g.twog
GROUP BY wordId
Usted debe asegurarse de que SQL Server utiliza un montón de índice agrupado busca (o loockups) para la ejecución de esta consulta.Debería ser la elección natural, pero a veces las estadísticas pueden estar dañadas o desactualizadas y SqlServer puede decidir que un escaneo completo sea más económico. Esto generalmente ocurre si no se conoce la cardinalidad de la tabla de la izquierda, por ejemplo, SqlServer puede suponer que la tabla de @word es masiva y millones de loockups van a ser más caros que una exploración de índice completa.