example - mysql varchar length

Encuentra los ngrams más largos en MySQL

Question

Dada una columna que contiene ngrams en un VARCHAR con utf8mb4_unicode_ci colación:

+---------------------------+
| ngram                     |
+---------------------------+
| stack overflow            |
| stack                     |
| overflow                  |
| stack overflow protection |
| overflow protection       |
| protection                |
+---------------------------+

Y una consulta:

SELECT * FROM ngrams WHERE ngram IN (''stack'', ''stack overflow'', ''protection'', ''overflow'')

Dadas las filas devueltas por esta consulta, ¿cómo puedo mantener solo las filas con los ngrams más largos de las filas devueltas ?

En este ejemplo, obtengo 3 filas: stack , stack overflow y protection .

Entonces, necesito filtrar filas como esta:

• Filtro la stack porque existe un stack overflow en las filas devueltas
• Mantengo el stack overflow , porque ninguna otra fila devuelta es un ngram que contiene stack overflow (hay stack overflow protection en la tabla, pero no está en las filas devueltas)
• Yo mantengo protection también
• Filtro el overflow , porque el stack overflow existe en las filas devueltas

Debe hacerse en MySQL debido a las colaciones (las comparaciones fuera de MySQL no darían los mismos resultados que en MySQL). (A menos que no conozca alguna función de MySQL que permita exponer la versión intercalada de una cadena).

Puedo pensar en la siguiente solución: ( sql fiddle )

SELECT  ngram
FROM    ngrams n1
WHERE   n1.ngram IN (''stack'', ''stack overflow'', ''protection'')
AND     NOT EXISTS (
    SELECT  1
    FROM    ngrams n2
    WHERE   n2.ngram IN (''stack'', ''stack overflow'', ''protection'')
    AND     LENGTH(n2.ngram) > LENGTH(n1.ngram)
    AND     CONCAT('' '', n2.ngram, '' '') LIKE CONCAT(''% '', n1.ngram, '' %'')
)

Sin embargo, es ineficiente, ya que la subconsulta se ejecutará para cada ngram coincidente.

Así que estoy buscando

• ya sea una manera de hacer esta consulta eficiente
• o una forma de hacer esto de manera confiable fuera de MySQL (teniendo en cuenta las intercalaciones)

Answer 1

Aquí hay una alternativa usando un JOIN IZQUIERDO.

La tabla se une automáticamente a condición de que no exista ningún ngram que esté contenido dentro de otro ngram y que no sea igual al ngram en la tabla autoincorporada. Se han evitado las subconsultas, teniendo en cuenta el rendimiento.

EDITAR :

Añadido condiciones de filtro.

SELECT n1.ngram
FROM ngrams n1
LEFT JOIN 
(
  SELECT ngram
  FROM ngrams
  WHERE ngram IN (''stack'', ''stack overflow'', ''protection'')) n2
ON n2.ngram like Concat(''%'', n1.ngram, ''%'') and n1.ngram <> n2.ngram
WHERE n2.ngram IS NULL
AND n1.ngram IN (''stack'', ''stack overflow'', ''protection'');

Si está comprobando si solo el inicio del ngram está contenido en otro ngram, puede reemplazar la condición de ON n2.ngram like Concat(n1.ngram, ''%'') and n1.ngram <> n2.ngram con ON n2.ngram like Concat(n1.ngram, ''%'') and n1.ngram <> n2.ngram .

Agregué más valores en el Fiddle de SQL:

1. ''xyz'' (que no está contenido en ningún otro ngram)
2. ''excepción de desbordamiento de pila'' (que es otro elemento primario de ''desbordamiento de pila'')
3. ''Manejo de excepciones de desbordamiento de pila'' (que es el padre de ''excepción de desbordamiento de pila'')

Demostración de SQL Fiddle

Referencia :

Sintaxis de JOIN en MySQL Reference Manual

Answer 2

Creo que puedes usar la unión interna propia en LIKE %original string% y elegir solo aquellas filas que tengan la longitud ngram igual a la longitud ngram unida más larga.

SELECT n1.* FROM ngrams n1
  INNER JOIN ngrams n2 ON
    n2.ngram LIKE CONCAT(''%'', `n1`.`ngram`, ''%'')
    AND n2.ngram IN ('''', ''stack'')
  WHERE n1.ngram IN ('''', ''stack'')
  GROUP BY n1.ngram
  HAVING MAX(CHAR_LENGTH(n2.ngram)) = CHAR_LENGTH(n1.ngram);

El inconveniente de esta solución es que necesita proporcionar su lista de cadenas dos veces.

Resulta que no es necesario proporcionar la lista dos veces:

SELECT n1.*
  FROM ngrams n1
  INNER JOIN ngrams n2 ON
    n2.ngram LIKE CONCAT(''%'', `n1`.`ngram`, ''%'')
    AND n2.ngram IN ('''', ''stack'')
  GROUP BY n1.ngram
  HAVING MAX(CHAR_LENGTH(n2.ngram)) = CHAR_LENGTH(n1.ngram);

Answer 3

Después de hacer esto sin mirar primero las otras soluciones, veo que es similar a su mejor solución existente, pero un poco más simple de leer y posiblemente un poco más eficiente;

SELECT n1.ngram
FROM ngrams n1
LEFT JOIN ngrams n2
  ON n2.ngram IN (''stack'', '''', ''protection'', ''overflow'')
 AND n1.ngram <> n2.ngram
 AND INSTR(n2.ngram, n1.ngram) > 0
WHERE n1.ngram IN (''stack'', '''', ''protection'', ''overflow'')
 AND n2.ngram IS NULL;

Un SQLfiddle para probar con .

Como no hay ningún cálculo en la línea AND n1.ngram <> n2.ngram , la consulta debería poder usar los índices de manera un poco más eficiente.

Answer 4

Está intentando filtrar los ngrams en la consulta en sí. Probablemente sea más eficiente hacerlo en dos pasos. Comience con una tabla con todos los ngrams posibles:

CREATE TABLE original (ngram varchar(100) NOT NULL)
GO

CREATE TABLE refined (ngram varchar(100) NOT NULL PRIMARY KEY)
GO

INSERT INTO original (ngram)
SELECT DISTINCT ngram
FROM ngrams
WHERE ngram IN (''stack'', '''', ''protection'')
GO

INSERT INTO refined (ngram)
SELECT ngram
FROM original

Luego borra los que no quieras. Para cada ngram, genere todas las subcadenas posibles. Para cada subcadena, elimine esa entrada (si existe) de la lista. Toma un par de bucles anidados, pero a menos que sus ngrams contengan una cantidad extremadamente grande de palabras, no debería tomar mucho tiempo.

CREATE PROCEDURE refine()
BEGIN
    DECLARE done INT DEFAULT FALSE;
    DECLARE words varchar(100);
    DECLARE posFrom, posTo int;
    DECLARE cur CURSOR FOR SELECT ngram FROM original;
    DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;

    OPEN cur;

    read_loop: LOOP
        FETCH cur INTO words;
        IF done THEN
            LEAVE read_loop;
        END IF;

        SET posFrom = 1;
        REPEAT
            SET posTo = LOCATE('' '', words, posFrom);
            WHILE posTo > 0 DO
                DELETE FROM refined WHERE ngram = SUBSTRING(words, posFrom, posTo - posFrom);
                SET posTo = LOCATE('' '', words, posTo + 1);
            END WHILE;
            IF posFrom > 1 THEN
                DELETE FROM refined WHERE ngram = SUBSTRING(words, posFrom);
            END IF;
            SET posFrom = LOCATE('' '', words, posFrom) + 1;
        UNTIL posFrom = 1 END REPEAT;
    END LOOP;

    CLOSE cur;
END

Lo que queda, es una tabla con solo los ngrams más largos:

CALL refine;

SELECT ngram FROM refined;

Fiddle de SQL: http://sqlfiddle.com/#!2/029dc/1/1

EDITAR: he añadido un índice en la tabla refined ; ahora debería funcionar en tiempo O (n) .

Answer 5

Esta ligera modificación a su consulta:

SELECT  ngram
FROM    ngrams n1
WHERE   n1.ngram IN (''stack'', '''', ''protection'') AND
        NOT EXISTS (SELECT  1
                    FROM    ngrams n2
                    WHERE   n2.ngram IN (''stack'', '''', ''protection'') AND
                            n2.ngram <> n1.ngram AND
                            n2.ngram LIKE CONCAT(''% '', n1.ngram, '' %'')
                   );

Debería ser bastante rápido con un índice en ngrams(ngram) . Tenga en cuenta que esto simplifica la condición like . No veo ninguna razón por la que debas preocuparte por los límites de las palabras. ¿Las "pilas" no serían una versión más larga de "pila"? (Aunque los elementos a los que se hace referencia con n-grams pueden ser palabras, los asocio con letras a menos que se indique lo contrario).

Con el índice, esto debería ser equivalente en rendimiento a otras soluciones que usan join .

Si tuviera que hacer esto un millón de veces y la tabla ngram no fuera demasiado grande, lo preprocesaría para obtener todos los pares de "generalizaciones" - ngram_pairs . Esto cambia lo anterior a

SELECT  ngram
FROM    ngrams n1
WHERE   n1.ngram IN (''stack'', '''', ''protection'') AND
        NOT EXISTS (SELECT  1
                    FROM    ngram_pairs np
                    WHERE   np.ngram1 = n1.ngram and
                            np.ngram2 in (''stack'', '''', ''protection'') 
                   )

Esto debería funcionar mucho mejor que el like con un índice en ngram_pairs(ngram1, ngram2) . El siguiente es el código para generar ngram_pairs :

create table ngram_pairs as
    select n1.ngram as ngram1, n2.ngram as ngram2
    from ngrams n1 join
         ngrams n2
         on length(n1.ngram) < length(n2.ngram) and
            n2.ngram like concat(''%'', n1.ngram, ''%'');

create index ngram_pairs_ngram1_ngram2 on ngram_pairs(ngram1, ngram2);

Answer 6

Intenta esta consulta usando la variable de usuario

select 
  ngram
from 
  (select 
    ngram, 
    @t:=if(@prev=rank, @t+1, 1) as num,
    @prev:=rank
  from 
    (select 
      ngram,
      @rank:=if(@prev like concat(ngram,''%''), @rank, @rank+1) as rank,
      CHAR_LENGTH(ngram) as size,
      @prev:=ngram
    from 
      tbl 
    join 
      (select 
         @prev:='''', 
         @rank:=1) t 
    where 
       ngram in ('''', ''stack'', ''protection'')
    order by 
       rank, size desc
   )t
  join 
    (select 
       @t:=0, 
       @prev:=0) t1
    ) t 
  where 
    num =1

Fiddle

|          NGRAM |
|----------------|
|  |
|     protection |

Answer 7

La siguiente consulta solo escanea los datos una vez y proporciona los resultados correctos ( fiddle ):

SELECT my_ngrams.ngram
  FROM (SELECT CASE WHEN @v LIKE CONCAT(''%'',n1.ngram,''%'') THEN 1 ELSE 0 END AS ngram_match
             , @v:=concat(@v,'','',n1.ngram) AS ngram_concat
             , n1.ngram
          FROM    ngrams n1, (SELECT @v := '''') r
         WHERE   n1.ngram IN (''stack'', '''', ''overflow'', ''protection'', ''overflow protection'')
      ORDER BY length(n1.ngram) DESC) my_ngrams
 WHERE my_ngrams.ngram_match <> 1
;

Sin embargo, se basa en el comportamiento de las variables definidas por el usuario en MySQL ( http://dev.mysql.com/doc/refman/5.5/en/user-variables.html ) y, como resultado, debe utilizarse con cierta precaución.

El "orden por" es importante para la solución, ya que afecta la forma en que la variable definida por el usuario se evalúa fila por fila, lo que afecta a las filas que coinciden con el caso y luego se filtran.

También concatena todos los resultados para buscar coincidencias de ngram antes de filtrar, por lo que debe tener en cuenta que podría terminar con una cadena concatenada que sea más ancha que el máximo permitido por MySQL ( http://dev.mysql.com/doc/refman/5.5/en/char.html ).

Esto debería ser muy eficiente incluso para tablas grandes siempre que la columna esté indexada correctamente.

Answer 8

Prueba este: Fiddle

SELECT * 
FROM   tab 
WHERE  ngram NOT IN (SELECT DISTINCT b.ngram 
                     FROM   tab a, 
                            tab b 
                     WHERE  a.ngram != b.ngram 
                            AND a.ngram LIKE Concat(''%'', b.ngram, ''%''));

Si desea incluir solo aquellos en la lista que existe en la tabla, intente esta consulta:

SELECT b.ngram ab 
FROM   (SELECT * 
        FROM   tab 
        WHERE  ngram IN ( ''stack'', '''', ''protection'' )) a, 
       (SELECT * 
        FROM   tab 
        WHERE  ngram IN ( ''stack'', '''', ''protection'' )) b 
WHERE  a.ngram LIKE Concat(''%'', b.ngram, ''%'') 
GROUP  BY b.ngram 
HAVING Count(*) = 1 

Demo2

Answer 9

Si entiendo su lógica correctamente, esta consulta debería darle el resultado correcto:

SELECT n1.ngram
FROM
  ngrams n1 LEFT JOIN ngrams n2
  ON
    n2.ngram IN (''stack'', '''', ''protection'')
    AND n2.ngram LIKE CONCAT(''%'', n1.ngram, ''%'')
    AND CHAR_LENGTH(n1.ngram) < CHAR_LENGTH(n2.ngram)
WHERE
  n1.ngram IN (''stack'', '''', ''protection'')
  AND n2.ngram IS NULL;

Por favor vea el violín here . Pero como espero que su tabla pueda tener muchos registros, mientras que su lista de palabras es muy limitada, ¿por qué no eliminar los ngrams más cortos de esta lista antes de ejecutar la consulta real? Mi idea es reducir la lista.

(''stack'', '''', ''protection'')

a

('''', ''protection'')

y esta consulta debe hacer el truco:

SELECT *
FROM
  ngrams
WHERE
  ngram IN (
    SELECT s1.ngram
    FROM (
      SELECT DISTINCT ngram
      FROM ngrams
      WHERE ngram IN (''stack'','''',''protection'')
    ) s1 LEFT JOIN (
      SELECT DISTINCT ngram
      FROM ngrams
      WHERE ngram IN (''stack'','''',''protection'')
    ) s2
      ON s2.ngram LIKE CONCAT(''%'', s1.ngram, ''%'')
         AND CHAR_LENGTH(s1.ngram) < CHAR_LENGTH(s2.ngram)
    WHERE
      s2.ngram IS NULL
  );

Sí, estoy consultando la tabla ngrams dos veces antes de unir nuevamente el resultado a ngrams , porque tenemos que asegurarnos de que el valor más largo realmente exista en la tabla, pero si tiene un índice adecuado en la columna ngram, las dos consultas derivadas que El uso de DISTINCT debería ser muy eficiente:

ALTER TABLE ngrams ADD INDEX idx_ngram (ngram);

El violín está here .

Editar:

Como señaló correctamente samuil, si solo necesita encontrar el ngram más corto y no todas las filas asociadas a él, no necesita la consulta externa y puede ejecutar la consulta interna. Con el índice adecuado, dos consultas SELECT DISTINCT serán muy eficientes, e incluso si la n2.ngram LIKE CONCAT(''%'', n1.ngram, ''%'') no puede optimizarse ( n2.ngram LIKE CONCAT(''%'', n1.ngram, ''%'') no puede aprovechar un índice) se ejecutará solo en unos pocos registros ya filtrados y debería ser bastante rápido.

Answer 10

Tratar

 ORDER BY LENGTH(ngram) DESC and use LIMIT 1

EDITAR:

trata eso :

  SELECT n1.ngram
  FROM ngrams n1 
  INNER JOIN ngrams n2
  ON LENGTH(n2.ngram) < LENGTH(n1.ngram)
  WHERE   n2.ngram IN (''stack'', '''', ''protection'')
  GROUP BY n1.ngram

Answer 11

SELECT  a.ngram FROM ngram a  CROSS JOIN (SELECT ngram AS ngram1 FROM ngram) b 
ON b.ngram1 LIKE CONCAT(''%'', a.ngram, ''%'') 
WHERE length(a.ngram) <= length(b.ngram1) 
GROUP BY a.ngram HAVING COUNT(a.ngram) = 1 ORDER BY LENGTH(b.ngram1) DESC

Answer 12

SELECT * FROM   ngrams a WHERE  a.n NOT IN (SELECT DISTINCT a.n 
                 FROM   ngrams b
                 WHERE b.n != a.n 
                    AND b.n LIKE CONCAT(''%'', a.n, ''%''));