Te doy la bienvenida a nuestra página web, en este sitio encontrarás la solucíon que buscas.
Solución:
El concepto de similitud de trigramas se basa en dividir cualquier oración en “trigramas” (secuencias de tres letras consecutivas) y tratar el resultado como un CONJUNTO (es decir, el orden no importa y usted no tiene valores repetidos). Antes de que se considere la oración, se agregan dos espacios en blanco al principio y uno al final, y los espacios simples se reemplazan por dobles.
Trigramas son un caso especial de N-gramos.
El conjunto de trigramas correspondiente a “Chateau blanc” se encuentra al encontrar todas las secuencias de tres letras que aparecen en él:
chateau blanc
--- => ' c'
--- => ' ch'
--- => 'cha'
--- => 'hat'
--- => 'ate'
--- => 'tea'
--- => 'eau'
--- => 'au '
--- => 'u '
--- => ' b'
--- => ' bl'
--- => 'bla'
--- => 'lan'
--- => 'anc'
--- => 'nc '
Ordenarlos y eliminar repeticiones te permite:
' b'
' c'
' bl'
' ch'
'anc'
'ate'
'au '
'bla'
'cha'
'eau'
'hat'
'lan'
'nc '
'tea'
Esto puede ser calculado por PostgreSQL mediante la función show_trgm:
SELECT show_trgm('Chateau blanc') AS A
A = [ b, c, bl, ch,anc,ate,au ,bla,cha,eau,hat,lan,nc ,tea]
… que tiene 14 trigramas. (Marque pg_trgm).
Y el conjunto de trigramas correspondiente a “Chateau Cheval Blanc” es:
SELECT show_trgm('Chateau Cheval Blanc') AS B
B = [ b, c, bl, ch,anc,ate,au ,bla,cha,che,eau,evl,hat,hev,la ,lan,nc ,tea,vla]
… que tiene 19 trigrams
Si cuenta cuántos trigramas tienen ambos conjuntos en común, encontrará que tienen los siguientes:
A intersect B =
[ b, c, bl, ch,anc,ate,au ,bla,cha,eau,hat,lan,nc ,tea]
y los que tienen en total son:
A union B =
[ b, c, bl, ch,anc,ate,au ,bla,cha,che,eau,evl,hat,hev,la ,lan,nc ,tea,vla]
Es decir, ambas frases tienen 14 trigramas en común y 19 en total.
La similitud se calcula como:
similarity = 14 / 19
Puedes comprobarlo con:
SELECT
cast(14.0/19.0 as real) AS computed_result,
similarity('Chateau blanc', 'chateau cheval blanc') AS function_in_pg
y verás que obtienes: 0.736842
… lo cual explica cómo se calcula la similitud, y por qué obtienes los valores que obtienes.
NOTA: Puede calcular la intersección y la unión mediante:
SELECT
array_agg(t) AS in_common
FROM
(
SELECT unnest(show_trgm('Chateau blanc')) AS t
INTERSECT
SELECT unnest(show_trgm('chateau chevla blanc')) AS t
ORDER BY t
) AS trigrams_in_common ;
SELECT
array_agg(t) AS in_total
FROM
(
SELECT unnest(show_trgm('Chateau blanc')) AS t
UNION
SELECT unnest(show_trgm('chateau chevla blanc')) AS t
) AS trigrams_in_total ;
Y esta es una forma de explorar la similitud de diferentes pares de oraciones:
WITH p AS
(
SELECT
'This is just a sentence I''ve invented'::text AS f1,
'This is just a sentence I''ve also invented'::text AS f2
),
t1 AS
(
SELECT unnest(show_trgm(f1)) FROM p
),
t2 AS
(
SELECT unnest(show_trgm(f2)) FROM p
),
x AS
(
SELECT
(SELECT count(*) FROM
(SELECT * FROM t1 INTERSECT SELECT * FROM t2) AS s0)::integer AS same,
(SELECT count(*) FROM
(SELECT * FROM t1 UNION SELECT * FROM t2) AS s0)::integer AS total,
similarity(f1, f2) AS sim_2
FROM
p
)
SELECT
same, total, same::real/total::real AS sim_1, sim_2
FROM
x ;
Puedes comprobarlo en Rextester
El algoritmo del trigrama debe ser más preciso cuanto menor sea la diferencia en la longitud de las cadenas comparadas. Puede modificar el algoritmo para compensar el efecto de la diferencia de longitud.
La siguiente función ejemplar reduce la similitud en un 1% para la diferencia de 1 carácter en string longitudes. Esto significa que favorece cadenas de la misma longitud (similar).
create or replace function corrected_similarity(str1 text, str2 text)
returns float4 language sql as $$
select similarity(str1, str2)* (1- abs(length(str1)-length(str2))/100.0)::float4
$$;
select
winery,
similarity(winery, 'chateau chevla blanc') as similarity,
corrected_similarity(winery, 'chateau chevla blanc') as corrected_similarity
from usr_wines
where winery % 'chateau chevla blanc'
order by corrected_similarity desc;
winery | similarity | corrected_similarity
--------------------------+------------+----------------------
Chateau ChevL Blanc | 0.85 | 0.8415
Chateau Cheval Blanc | 0.727273 | 0.727273
Chateau Cheval Blanc | 0.727273 | 0.727273
Chateau Cheval Blanc | 0.727273 | 0.727273
Chateau Blanc, | 0.736842 | 0.692632
Chateau Blanc | 0.736842 | 0.685263
Chateau Blanc | 0.736842 | 0.685263
Chateau Blanc | 0.736842 | 0.685263
Chateau Blanc | 0.736842 | 0.685263
Chateau Blanc | 0.736842 | 0.685263
Chateau Cheval Blanc (7) | 0.666667 | 0.64
Chateau Du Cheval Blanc | 0.64 | 0.6208
Chateau Du Cheval Blanc | 0.64 | 0.6208
Chateau Cheval Blanc Cbo | 0.64 | 0.6144
(14 rows)
De manera similar, puede corregir la similitud estándar, por ejemplo, cuántos caracteres iniciales son idénticos (aunque la función será un poco más complicada).
A veces quieres lo opuesto a la respuesta de klin. Hay aplicaciones donde una gran diferencia en string las longitudes no deben dar lugar a una penalización de puntuación tan significativa.
Por ejemplo, imagine un formulario de resultados de autocompletar con sugerencias de concordancia de trigramas que mejoran a medida que escribe.
Aquí hay una forma alternativa de igualar la puntuación que todavía usa trigramas pero favorece las coincidencias de subcadenas un poco más de lo habitual.
En cambio, la fórmula de la similitud comienza con
the number of common trigrams
-------------------------------------------
the number of trigrams in the shortest word <-- key difference
y puede aumentar desde allí en función de una buena puntuación de similitud estándar.
CREATE OR REPLACE FUNCTION substring_similarity(string_a TEXT, string_b TEXT) RETURNS FLOAT4 AS $$
DECLARE
a_trigrams TEXT[];
b_trigrams TEXT[];
a_tri_len INTEGER;
b_tri_len INTEGER;
common_trigrams TEXT[];
max_common INTEGER;
BEGIN
a_trigrams = SHOW_TRGM(string_a);
b_trigrams = SHOW_TRGM(string_b);
a_tri_len = ARRAY_LENGTH(a_trigrams, 1);
b_tri_len = ARRAY_LENGTH(b_trigrams, 1);
IF (NOT (a_tri_len > 0) OR NOT (b_tri_len > 0)) THEN
IF (string_a = string_b) THEN
RETURN 1;
ELSE
RETURN 0;
END IF;
END IF;
common_trigrams := ARRAY(SELECT UNNEST(a_trigrams) INTERSECT SELECT UNNEST(b_trigrams));
max_common = LEAST(a_tri_len, b_tri_len);
RETURN COALESCE(ARRAY_LENGTH(common_trigrams, 1), 0)::FLOAT4 / max_common::FLOAT4;
END;
$$ LANGUAGE plpgsql;
CREATE OR REPLACE FUNCTION corrected_similarity(string_a TEXT, string_b TEXT)
RETURNS FLOAT4 AS $$
DECLARE
base_score FLOAT4;
BEGIN
base_score := substring_similarity(string_a, string_b);
-- a good standard similarity score can raise the base_score
RETURN base_score + ((1.0 - base_score) * SIMILARITY(string_a, string_b));
END;
$$ LANGUAGE plpgsql;
CREATE OR REPLACE FUNCTION is_minimally_substring_similar(string_a TEXT, string_b TEXT) RETURNS BOOLEAN AS $$
BEGIN
RETURN corrected_similarity(string_a, string_b) >= 0.5;
END;
$$ LANGUAGE plpgsql;
CREATE OPERATOR %%% (
leftarg = TEXT,
rightarg = TEXT,
procedure = is_minimally_substring_similar,
commutator = %%%
);
Ahora puede usar esto de la misma manera que la consulta de similitud estándar:
SELECT * FROM table WHERE name %%% 'chateau'
ORDER BY corrected_similarity(name, 'chateau') DESC;
Rendimiento
El rendimiento es aceptable para un espacio de búsqueda de 100K registros, pero probablemente no sería bueno para un espacio de búsqueda de millones. Para eso, es posible que desee utilizar una compilación modificada del módulo pg_trgm, código en github.