Come posso rilevare sottostringhe comuni in un elenco di stringhe

https://stackoverflow.com/questions/1410822

05-07-2019
|

Domanda

Dato un set di stringhe, ad esempio:

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

Voglio essere in grado di rilevare che si tratta di tre set di file:

entires [1,2]
J27 [Rosso, Verde] P [1,2]
JournalP [1,2] [Rosso, Verde, Blu]

Esistono modi noti per affrontare questo problema - qualsiasi documento pubblicato che posso leggere su questo?

L'approccio che sto prendendo in considerazione è per ogni stringa guardare tutte le altre stringhe e trovare i caratteri comuni e dove sono i caratteri diversi, cercando di trovare gruppi di stringhe che hanno più in comune, ma temo che questo non sia molto efficiente e può dare falsi positivi.

Nota che questo non è lo stesso di ' Come posso rilevare gruppi di stringhe comuni nei nomi dei file " perché ciò presuppone che una stringa abbia sempre una serie di cifre che la seguono.

Soluzione

Vorrei iniziare qui: http://en.wikipedia.org/wiki/Longest_common_substring_problem

Esistono collegamenti a informazioni supplementari nei collegamenti esterni, comprese le implementazioni Perl dei due algoritmi spiegati nell'articolo.

Modificato per aggiungere:

Sulla base della discussione, continuo a pensare che il substrato comune più lungo possa essere al centro di questo problema. Anche nell'esempio Journal che fai riferimento nel tuo commento, la caratteristica che definisce quell'insieme è la sottostringa "Journal".

Vorrei prima considerare ciò che definisce un set come separato dagli altri set. Questo ti dà la tua partizione per dividere i dati, e quindi il problema è nel misurare quanta comunanza esiste all'interno di un set. Se la caratteristica di definizione è una sottostringa comune, allora Sottostringa comune più lunga sarebbe un punto di partenza logico.

Per automatizzare il processo di rilevamento dei set, in generale, avrai bisogno di una misura a coppie di comunanza che puoi usare per misurare la 'differenza' tra tutte le coppie possibili. Quindi è necessario un algoritmo per calcolare la partizione che determina la differenza totale più bassa complessiva. Se la misura della differenza non è Sottostringa comune più lunga, va bene, ma è necessario determinare quale sarà. Ovviamente deve essere qualcosa di concreto che puoi misurare.

Tieni presente anche che le proprietà della tua misurazione della differenza si baseranno sugli algoritmi che possono essere utilizzati per creare la partizione. Ad esempio, supponiamo che diff (X, Y) dia la misura della differenza tra X e Y. Quindi sarebbe probabilmente utile se la tua misura della distanza fosse tale che diff (A, C) & Lt; = diff (A, B) + diff (B, C). E ovviamente diff (A, C) dovrebbe essere uguale a diff (C, A).

Nel pensare a questo, comincio anche a chiedermi se potremmo concepire la 'differenza' come distanza tra due stringhe e, con una definizione rigorosa della distanza, potremmo quindi tentare una sorta di analisi dei cluster sulle stringhe di input. Solo un pensiero.

Altri suggerimenti

Ottima domanda! I passaggi per una soluzione sono:

tokenizing input
utilizzo di token per creare una struttura dati appropriata. un DAWG è l'ideale, ma un Trie è più semplice e un punto di partenza decente.
post-elaborazione facoltativa della struttura dei dati per semplificare o raggruppare le sottostrutture in output separati
serializzazione della struttura dei dati in una espressione regolare o sintassi simile

Ho implementato questo approccio in regroup.py . Ecco un esempio:

$ 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))

Qualcosa del genere potrebbe funzionare.

Crea un trie che rappresenti tutte le tue stringhe.

Nell'esempio che hai fornito, ci sarebbero due bordi dalla radice: " E " e " J " ;. Il & Quot; J & Quot; il ramo sarebbe quindi diviso in " Jo " e " J2 " ;.

Un singolo filo che forca, ad es. E-n-t-i-r-e-S- (forchette a 1, 2) indica una scelta, quindi sarebbe Intero [1,2]
Se il filo è " troppo corto " in relazione alla forcella, ad es. BA- (fork a NANA e HAMAS), elenchiamo due parole (& Quot; banana, bahamas & Quot;) piuttosto che una scelta (& Quot; ba [nana, hamas] & Quot; ). " Troppo breve " potrebbe essere semplice come " se la parte dopo la forcella è più lunga della parte precedente " o forse ponderata dal numero di parole che hanno un prefisso specificato.
Se due sottotitoli sono " " sufficientemente simili; quindi possono essere uniti in modo che invece di un albero, ora si abbia un grafico generale. Ad esempio se hai ABRed, ABBlue, ABGreen, CDRed, CDBlue, CDGreen, potresti trovare che la sottostruttura è radicata su & Quot; AB & Quot; è lo stesso della sottostruttura radicata in " CD " ;, quindi li uniresti. Nel tuo output questo sarà simile al seguente: [ramo sinistro, ramo destro] [sottostruttura], quindi: [AB, CD] [Rosso, Blu, Verde]. Come affrontare i sottotitoli vicini ma non esattamente uguali? Probabilmente non c'è una risposta assoluta, ma qualcuno qui potrebbe avere una buona idea.

Sto contrassegnando questa risposta wiki della community. Non esitate a estenderlo in modo che, insieme, potremmo avere una risposta ragionevole alla domanda.

Esistono molti approcci alla somiglianza delle stringhe. Suggerirei di dare un'occhiata a questa libreria open source che implementa molte metriche come la distanza di Levenshtein.

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

Dovresti essere in grado di raggiungere questo obiettivo con alberi di suffisso generalizzati: cerca lunghi percorsi nell'albero di suffissi che provengono da più stringhe di origine.

prova " frak " . Crea un'espressione regex dall'insieme di stringhe. Forse qualche modifica di esso ti aiuterà. https://github.com/noprompt/frak

Spero che sia d'aiuto.

Ci sono molte soluzioni proposte che risolvono il caso generale di trovare sottostringhe comuni. Tuttavia, il problema qui è più specializzato. Stai cercando prefissi comuni, non solo sottostringhe. Questo lo rende un po 'più semplice. Una bella spiegazione per trovare il prefisso comune più lungo è disponibile all'indirizzo http://www.geeksforgeeks.org / lungo-common-prefix-set-1-parola per parola-matching /

Quindi la mia proposta " pythonese " lo pseudo-codice è qualcosa del genere (fare riferimento al collegamento per un'implementazione di 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

Per questo particolare esempio di stringhe per mantenerlo estremamente semplice prendere in considerazione l'uso di una semplice parola / cifra-separazione.

Apparentemente una sequenza senza cifre può iniziare con la lettera maiuscola (intera). Dopo aver suddiviso tutte le stringhe in gruppi di sequenze, qualcosa come

[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]

Quindi inizia a raggruppare per gruppi, puoi presto vedere quel prefisso " Intero " è un comune per alcuni gruppi e che tutti i sottogruppi hanno S come headgroup, quindi solo la variabile per questi è 1,2. Per il caso J27 puoi vedere che J27 è solo foglia, ma che poi si ramifica in rosso e verde.

Quindi un po 'di List < Pair < list, string > > -struttura (modello composito se ricordo bene).

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

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow