¿Cómo detectar y analizar patrones similares como Excel?

Question

Conoce la funcionalidad en Excel cuando escribe 3 filas con un patrón determinado y arrastra la columna hasta el final Excel intenta continuar el patrón por usted.

Por ejemplo

Tipo ...

• prueba-1
• prueba-2
• prueba-3

Excel continuará con:

• prueba-4
• prueba-5
• prueba-n ...

mismas obras de algunos otros patrones como las fechas y así sucesivamente.

estoy tratando de lograr algo similar pero también quiero para manejar los casos más excepcionales, tales como:

• prueba-azul-somethingelse
• prueba-amarillo-somethingelse
• prueba-roja -somethingelse

Ahora basado en esta entradas que quiero decir que el patrón es:

• los Ensayos [DINÁMICO] -algo

continuar la [DINÁMICO] con otros colores es toda otra cosa, realmente no me importa eso ahora. Estoy más que interesado en detectar las partes [DYNAMIC] en el patrón.

Necesito detectar esto de una gran cantidad de entradas de la piscina. Supongamos que tiene 10.000 cadenas con este tipo de patrones, y desea agrupar estas cadenas en función de la similitud y también detectar qué parte del texto cambia constantemente ([DINÁMICO]).

La clasificación de documentos puede ser útil en este escenario, pero no estoy seguro de por dónde empezar.

ACTUALIZACIÓN:

me olvidó mencionar que también es posible tener varios patrones [Dinámico].

Tales como:

• test_ [DINÁMICO] [DYNAMIC2]

no creo que es importante, pero tengo la intención de implementar esto en.NET, pero cualquier sugerencia sobre los algoritmos a usar sería bastante útil.

Answer 1

Tan pronto como comience a considerar encontrar partes dinámicas de patrones del formulario: <const1><dynamic1><const2><dynamic2>.... sin ninguna otra suposición, entonces necesitaría encontrar el longest common subsequence de las cadenas de muestra que ha proporcionado. Por ejemplo, si tengo test-123-abc y test-48953-defg, entonces el LCS sería test- y -. Las partes dinámicas serían entonces las brechas entre el resultado del LCS. Luego puede buscar su parte dinámica en una estructura de datos adecuada.

El problema de encontrar el LCS de más de 2 cadenas es muy costoso, y este sería el cuello de botella de su problema. A costa de la precisión, puedes hacer que este problema sea manejable. Por ejemplo, puede realizar LCS entre todos los pares de cadenas y agrupar conjuntos de cadenas con resultados de LCS similares. Sin embargo, esto significa que algunos patrones no se identificarán correctamente.

Por supuesto, todo esto puede evitarse si puede imponer restricciones adicionales a sus cadenas, como Excel, que solo parece permitir patrones del formulario <const><dynamic>.

Answer 2

encontrar [dinámico] no es gran cosa, puedes hacer eso con 2 cuerdas: simplemente comienza al principio y para cuando empiezan a no ser iguales, haz lo mismo desde el final, y listo - tú tiene su [dinámica]

algo así como (pseudo - un poco):

String s1 = 'asdf-1-jkl'; 
String s2= 'asdf-2-jkl'; 
int s1I = 0, s2I = 0; 
String dyn1, dyn2; 
for (;s1I<s1.length()&&s2I<s2.length();s1I++,s2I++) 
    if (s1.charAt(s1I) != s2.charAt(s2I)) 
    break; 
int s1E = s1.length(), s2E = s2.length; 
for (;s2E>0&&s1E>0;s1E--,s2E--) 
    if (s1.charAt(s1E) != s2.charAt(s2E)) 
    break; 
dyn1 = s1.substring(s1I, s1E); 
dyn2 = s2.substring(s2I, s2E); 

Sobre sus 10k conjuntos de datos. Debería llamar a esto (o tal vez a una versión un poco más optimizada) con cada combinación para descubrir su patten (llamadas de 10k x 10k). y luego ordenar el resultado por patrón (es decir, guardar el inicio y el final y ordenar por estos campos)

Answer 3

Creo que lo que necesita es calcular algo como Levenshtein distance, para encontrar el grupo de cadenas similares, y luego en cada grupo de cadenas similares, identifica la parte dinámica en un algoritmo típico similar a un diff.

Answer 4

Google docs podría ser mejor que sobresalir para este tipo de cosas, lo creas o no.

Google ha recopilado cantidades masivas de datos en conjuntos; por ejemplo, en el ejemplo que usted dio reconocería el azul, rojo, amarillo ... como parte del conjunto 'colores'. Tiene un reconocimiento de patrones mucho más completo que Excel, por lo que tendría más posibilidades de continuar el patrón.