¿Cómo puedo detectar subcadenas comunes en una lista de cadenas

Question

Dado un conjunto de cadenas, por ejemplo:

EFgreen 
EFgrey 
EntireS1 
EntireS2 
J27RedP1 
J27GreenP1 
J27RedP2 
J27GreenP2 
JournalP1Black 
JournalP1Blue 
JournalP1Green 
JournalP1Red 
JournalP2Black 
JournalP2Blue 
JournalP2Green 

Quiero ser capaz de detectar que se trata de tres conjuntos de archivos:

• entires [1,2]
• J27 [rojo, verde] P [1,2]
• JournalP [1,2] [rojo, verde, azul]

¿Hay alguna forma conocida de abordar este problema, cualquier documento publicado que pueda leer al respecto?

El enfoque que estoy considerando es para cada cadena de todas las demás cadenas y encontrar los caracteres comunes y donde están los diferentes caracteres, tratando de encontrar conjuntos de cadenas que tienen más en común, pero me temo que esto no es muy eficiente y puede dar falsos positivos.

Tenga en cuenta que esto no es lo mismo que 'How do I detect groups of common strings in filenames' porque eso supone que una cadena siempre tendrá una serie de dígitos a continuación.

Answer 1

Me gustaría empezar aquí: http://en.wikipedia.org/wiki/Longest_common_substring_problem

Hay enlaces a información complementaria en los enlaces externos, incluyendo implementaciones de Perl de los dos algoritmos explicados en el artículo.

Editado para añadir:

Sobre la base de la discusión, aún pienso común más larga Subcadena podría estar en el centro de este problema. Incluso en el ejemplo de la revista que hace referencia en su comentario, la característica definitoria de ese conjunto es la subcadena 'Diario'.

Primero consideraría qué define un conjunto como separado de los otros conjuntos. Eso le da a su partición para dividir los datos, y luego el problema está en medir la cantidad de elementos comunes dentro de un conjunto. Si la característica definitoria es una subcadena común, entonces la subcadena común más larga sería un punto de inicio lógico.

Para automatizar el proceso de detección de conjuntos, en general, necesitará una medida pareja de elementos comunes que puede usar para medir la "diferencia" entre todos los pares posibles. Luego necesita un algoritmo para calcular la partición que resulta en la diferencia total más baja en general. Si la medida de diferencia no es la subcadena común más larga, está bien, pero luego debe determinar cuál será. Obviamente tiene que ser algo concreto que puedas medir.

Tenga en cuenta también que las propiedades de la medición de diferencia se aplicarán a los algoritmos que se pueden usar para crear la partición. Por ejemplo, suponga que diff (X, Y) da la medida de la diferencia entre X e Y. Entonces probablemente sería útil si su medida de distancia fuera tal que diff (A, C) < = diff (A, B) + diff (ANTES DE CRISTO). Y obviamente diff (A, C) debería ser lo mismo que diff (C, A).

Al pensar en esto, también empiezo a preguntarme si podríamos concebir la 'diferencia' como una distancia entre dos cuerdas, y, con una definición rigurosa de la distancia, podríamos intentar algún tipo de cluster analysis en las cadenas de entrada. Solo un pensamiento.

Answer 2

Existen muchos enfoques para la similitud de cadenas. Sugeriría echarle un vistazo a esta biblioteca de código abierto que implementa muchas métricas como la distancia de Levenshtein.

http://sourceforge.net/projects/simmetrics/

Answer 3

Algo así podría funcionar.

1. Construye un trie que represente todas tus cadenas.

En el ejemplo que proporcionó, habría dos bordes desde la raíz: "E" y "J". La rama "J" se dividiría en "Jo" y "J2".

2. Una sola hebra que se bifurca, p. E-n-t-i-r-e-S- (horquillas a 1, 2) indica una opción, por lo que sería EntireS [1,2]

3. Si el cordón es "demasiado corto" en relación con la horquilla, p. B-A- (se bifurca a N-A-N-A y H-A-M-A-S), enumeramos dos palabras ("banana, bahamas") en lugar de una opción ("ba [nana, hamas]"). "Demasiado corto" podría ser tan simple como "si la parte posterior a la horquilla es más larga que la parte anterior", o tal vez ponderada por el número de palabras que tienen un prefijo dado.

4. Si dos subárboles son "suficientemente similares", entonces se pueden combinar para que en lugar de un árbol, ahora tenga un gráfico general. Por ejemplo, si tiene ABRed, ABBlue, ABGreen, CDRed, CDBlue, CDGreen, puede encontrar que el subárbol enraizado en "AB" es el mismo que el subárbol enraizado en "CD", por lo que los fusionaría. En su salida, esto se verá así: [rama izquierda, rama derecha] [subárbol], entonces: [AB, CD] [Rojo, Azul, Verde]. ¿Cómo lidiar con los subárboles que están cerca pero no exactamente iguales? Probablemente no haya una respuesta absoluta, pero alguien aquí puede tener una buena idea.

Estoy marcando esta comunidad de respuesta wiki. Siéntase libre de extenderlo para que, juntos, podamos tener una respuesta razonable a la pregunta.

Answer 4

Para este ejemplo particular de cadenas para mantenerlo extremadamente simple, considere usar una separación simple de palabra/dígito.

Aparentemente, una secuencia sin dígitos puede comenzar con mayúscula (Completa). Después de romper todas las cadenas en grupos de secuencias, algo así como

[Entire][S][1] 
[Entire][S][2] 
[J][27][Red][P][1] 
[J][27][Green][P][1] 
[J][27][Red][P][2] 
.... 
[Journal][P][1][Blue] 
[Journal][P][1][Green] 

A continuación, iniciar la agrupación por grupos, puede muy pronto ver que el prefijo "Todo" es una común para algún grupo y que todos los subgrupos tienen S como grupo de cabeza, por lo La única variable para esos es 1,2. Para el caso J27, puede ver que J27 es solo una hoja, pero que luego se ramifica en rojo y verde.

Así somekind de Lista < Par lista <, cadena > > -estructura (patrón compuesto si no recuerdo mal).

Answer 5

Debería poder lograr esto con árboles de sufijo generalizados: busque las rutas largas en el árbol de sufijos que provienen de múltiples cadenas de origen.

Answer 6

import java.util.*; 
class StringProblem 
{ 
    public List<String> subString(String name) 
    { 
     List<String> list=new ArrayList<String>(); 
     for(int i=0;i<=name.length();i++) 
     { 
      for(int j=i+1;j<=name.length();j++) 
      { 
       String s=name.substring(i,j); 
       list.add(s); 
      } 
     } 
     return list; 
    } 
    public String commonString(List<String> list1,List<String> list2,List<String> list3) 
    { 
     list2.retainAll(list1); 
     list3.retainAll(list2); 

     Iterator it=list3.iterator(); 
     String s=""; 
     int length=0; 
     System.out.println(list3); // 1 1 2 3 1 2 1 
     while(it.hasNext())  
     { 
      if((s=it.next().toString()).length()>length) 
      { 
       length=s.length(); 
      } 
     } 
     return s; 
    } 
    public static void main(String args[]) 
    { 
     Scanner sc=new Scanner(System.in); 
     System.out.println("Enter the String1:"); 
     String name1=sc.nextLine(); 
     System.out.println("Enter the String2:"); 
     String name2=sc.nextLine(); 
     System.out.println("Enter the String3:"); 
     String name3=sc.nextLine(); 
     // String name1="salman"; 
     // String name2="manmohan"; 
     // String name3="rahman"; 

     StringProblem sp=new StringProblem(); 

     List<String> list1=new ArrayList<String>(); 
     list1=sp.subString(name1); 

     List<String> list2=new ArrayList<String>(); 
     list2=sp.subString(name2); 


     List<String> list3=new ArrayList<String>(); 
     list3=sp.subString(name3); 

     sp.commonString(list1,list2,list3); 
     System.out.println(" "+sp.commonString(list1,list2,list3)); 
    } 
} 

Answer 7

prueba "frak". Crea expresión regex a partir de un conjunto de cadenas. Quizás alguna modificación lo ayudará. https://github.com/noprompt/frak

Espero que ayude.

Answer 8

¡Una gran pregunta!Los pasos para una solución son:

1. tokenizing entrada
2. usando tokens para construir un apropiado data structure. un DAWG es ideal, pero un Trie es más simple y un punto de partida decente.
3. opcional de post-procesamiento de la estructura de datos para la simplificación o agrupación de los subárboles en salidas separadas
4. serialization de la estructura de datos para una sintaxis

regular expression o similares he implementado este enfoque en regroup.py. Aquí hay un ejemplo:

$ cat | ./regroup.py --cluster-prefix-len=2 
EFgreen 
EFgrey 
EntireS1 
EntireS2 
J27RedP1 
J27GreenP1 
J27RedP2 
J27GreenP2 
JournalP1Black 
JournalP1Blue 
JournalP1Green 
JournalP1Red 
JournalP2Black 
JournalP2Blue 
JournalP2Green 
^D 
EFgre(en|y) 
EntireS[12] 
J27(Green|Red)P[12] 
JournalP[12](Bl(ack|ue)|(Green|Red)) 

Answer 9

Se han propuesto muchas soluciones que resuelven el caso general de búsqueda de subcadenas comunes. Sin embargo, el problema aquí es más especializado. Está buscando prefijos comunes, no solo subcadenas. Esto lo hace un poco más simple. Una explicación agradable para encontrar prefijo común más larga se pueden encontrar en http://www.geeksforgeeks.org/longest-common-prefix-set-1-word-by-word-matching/

Así que mi propuesta "pythonese" pseudo-código es algo como esto (se refiere al enlace de una implementación de find_lcp:

def count_groups(items): 
    sorted_list = sorted(items) 

    prefix = sorted_list[0] 
    ctr = 0 
    groups = {} 
    saved_common_prefix = "" 
    for i in range(1, sorted_list): 
    common_prefix = find_lcp(prefix, sorted_list[i]) 
    if len(common_prefix) > 0: #we are still in the same group of items 
     ctr += 1 
     saved_common_prefix = common_prefix 
     prefix = common_prefix 
    else: # we must have switched to a new group 
     groups[saved_common_prefix] = ctr 
     ctr = 0 
     saved_common_prefix = "" 
     prefix = sorted_list[i] 
    return groups