algorithm - programacion - python separar string por caracter

¿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 estos son tres conjuntos de archivos:

• TodaS [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 ver todas las demás cadenas y encontrar los caracteres comunes y donde están los diferentes personajes, 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 ''¿Cómo puedo detectar grupos de cadenas comunes en nombres de archivos'' porque eso supone que una cadena siempre tendrá una serie de dígitos a continuación?

Answer 1

Algo así podría funcionar.

1. Construye un trie que represente todas tus cadenas.

En el ejemplo que dio, 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, por ejemplo, WholeS- (tenedores a 1, 2) indica una elección, por lo que sería WholeS [1,2]

3. Si el hilo es "demasiado corto" en relación con la horquilla, por ejemplo BA- (se bifurca a NANA y HAMAS), 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 pueden fusionarse 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 respuesta comunidad wiki. Siéntase libre de extenderlo para que, juntos, podamos tener una respuesta razonable a la pregunta.

Answer 2

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

Answer 3

Empezaría aquí: http://en.wikipedia.org/wiki/Longest_common_substring_problem

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

Editado para agregar:

Basado en la discusión, todavía creo que la subcadena común más larga podría estar en el corazón 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 conjunta 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 su 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 cadenas y, con una definición rigurosa de la distancia, ¿podríamos intentar algún tipo de análisis de conglomerados en las cadenas de entrada? . Solo un pensamiento.

Answer 4

Gran pregunta! Los pasos para una solución son:

1. entrada de tokenizing
2. usando tokens para construir una estructura de datos apropiada. un DAWG es ideal, pero un Trie es más simple y un punto de partida decente.
3. procesamiento posterior opcional de la estructura de datos para la simplificación o la agrupación de subárboles en salidas separadas
4. serialization de la estructura de datos a una expresión regular o sintaxis similar

Implementé 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 5

Hay muchas soluciones propuestas que resuelven el caso general de encontrar 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 buena explicación para encontrar el prefijo común más largo se puede encontrar en http://www.geeksforgeeks.org/longest-common-prefix-set-1-word-by-word-matching/

Por lo tanto, mi pseudocódigo "pythonese" propuesto es algo como esto (consulte el enlace para 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

Answer 6

Hay 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 7

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

Una secuencia sin dígitos aparentemente puede comenzar con mayúscula (Completa). Después de dividir 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]

Luego comience a agrupar por grupos, puede ver muy pronto que el prefijo "Completo" es común para algún grupo y que todos los subgrupos tienen S como grupo de cabeza, por lo que solo la variable para ellos 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í que algún tipo de lista <Pair <list, string >> -structure (patrón compuesto si no recuerdo mal).

Answer 8

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

Espero eso ayude.

Answer 9

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));
    }
}