Trova la più piccola stringa univoco per ogni stringa in un array

Question

(sto scrivendo questo nel contesto di JavaScript, ma accetterà una risposta corretta algoritmicamente in qualsiasi lingua)

Come si fa a trovare la sottostringa più corta di ogni elemento in una matrice di stringhe in cui la sottostringa NON è contenuta in nessuno degli altri elementi, ignorando il caso?

Supponiamo che io sono una serie di input come ad esempio:

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"]; 

L'output dovrebbe essere qualcosa del tipo:

var uniqueNames = ["ne", "h", "ua", "ka", "i", "r"]; 

Per i miei scopi, si può tranquillamente supporre che nessun elemento sarà interamente dentro un altro elemento

I miei pensieri:
Sembra che uno potrebbe probabilmente forza bruta questo, lungo le linee di:

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"]; 
var uniqueNames = [], nameInd, windowSize, substrInd, substr, otherNameInd, foundMatch; 
// For each name 
for (nameInd = 0; nameInd < names.length; nameInd++) 
{ 
    var name = names[nameInd]; 
    // For each possible substring length 
    windowLoop: 
    for (windowSize = 1; windowSize <= name.length; windowSize++) 
    { 
     // For each starting index of a substring 
     for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++) 
     { 
      substr = name.substring(substrInd,substrInd+windowSize).toLowerCase(); 
      foundMatch = false; 
      // For each other name 
      for (otherNameInd = 0; otherNameInd < names.length; otherNameInd++) 
      { 
       if (nameInd != otherNameInd && names[otherNameInd].toLowerCase().indexOf(substr) > -1) 
       { 
        foundMatch = true; 
        break; 
       } 
      } 

      if (!foundMatch) 
      { 
       // This substr works! 
       uniqueNames[nameInd] = substr; 
       break windowLoop; 
      } 
     } 
    } 
} 

Ma devo immaginare che ci sia una soluzione più elegante utilizzando tentativi/alberi prefisso, array suffisso, o qualcosa di interessante come quello.

Edit: Credo che questa è la forma della risposta selezionata avrebbe preso a livello di codice in JavaScript:

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"]; 
var uniqueNames = [], permutations = {}, permutation, nameInd, windowSize, substrInd, substr; 

// For each name 
for (nameInd = 0; nameInd < names.length; nameInd++) 
{ 
    var name = names[nameInd]; 
    // For each possible substring length 
    windowLoop: 
    for (windowSize = 1; windowSize <= name.length; windowSize++) 
    { 
     // For each starting index of a substring 
     for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++) 
     { 
      substr = name.substring(substrInd,substrInd+windowSize).toLowerCase(); 
      permutations[substr] = (typeof permutations[substr] === "undefined")?nameInd:-1; 
     } 
    } 
} 

for (substr in permutations) 
{ 
    permutation = permutations[substr]; 
    if (permutation !== -1 && ((typeof uniqueNames[permutation] === "string" && substr.length < uniqueNames[permutation].length) || typeof uniqueNames[permutation] === "undefined")) 
    { 
     uniqueNames[permutation] = substr; 
    } 
} 

Answer 1

Say N è il numero di stringhe e L è la lunghezza massima di stringa. Stai facendo fino a N*L*L*N iterazioni.

Posso solo migliorare un po 'scambiando un'iterazione per memoria extra. Per ogni possibile lunghezza stringa (L iterazioni),

• enumerare tutte le sottostringhe di lunghezza che in ciascuna (N*L), e memorizzarlo tra con indice di nome in una tabella hash (1). Se esiste già un indice per questa sottostringa, sai che non funzionerà, quindi sostituisci l'indice con un valore speciale, come -1.

• piedi la tabella hash, raccogliendo sottostringhe per i quali non è indice di -1 - che sono le risposte per i loro indici corrispondenti, ma solo usarli se i nomi che non hanno già una risposta più breve da una precedente iterazione

L'utilizzo della memoria può essere notevolmente ridotto memorizzando il riferimento nella stringa esistente anziché copiare le sottostringhe.

Answer 2

Questo problema può essere risolto in O (N * L * L * L) complessità. L'approccio utilizzerà i suffissi try. Ogni nodo del trie memorizzerà anche il conteggio prefisso che farà riferimento al numero di volte in cui la sottostringa formata durante il passaggio a quel nodo dalla radice è apparsa in tutti i suffissi inseriti fino ad ora.

Ci impegneremo a provare N + 1.Il primo trie sarà globale e inseriremo tutti i suffissi di tutte le N stringa in esso. I successivi tentativi di N saranno locali per ciascuna delle stringhe N contenenti suffissi corrispondenti.

Questa fase di preelaborazione della costruzione di tentativi verrà eseguita in O (N * L * L).

Ora una volta che i tentativi sono stati costruiti, per ciascuna stringa, si può iniziare quering il numero di volte che una stringa (partendo dalla lunghezza minima) è verificato nel trie globale e il trie corrispondente a tale stringa. Se è uguale in entrambi, allora implica che non è incluso in nessun'altra stringa tranne se stessa. Questo può essere ottenuto in O (N * L * L * L). La complessità può essere spiegata come N per ogni stringa, L * L per considerare ogni sottostringa e L per eseguire query nel trie.

Answer 3

Se si genera un albero di suffisso generalizzato, è sufficiente trovare il punto più basso in cui un infisso di ogni stringa si dirama dagli infissi delle altre stringhe e portare l'etichetta a quel punto di diramazione più una "distinzione" carattere. Il kicker è che deve esserci un carattere extra (potrebbe essere ramificato solo al metacarattere bloccato all'estremità di ogni stringa), e il punto di diramazione potrebbe non portare a una foglia, potrebbe portare a un sottoalbero con foglie tutte della stessa stringa (quindi i nodi interni devono essere considerati).

Per ogni stringa S trovare il nodo N più superficiale (per profondità dell'etichetta padre) che contiene solo foglie di S e la cui etichetta bordo contiene almeno un carattere. L'etichetta del percorso dalla radice al genitore di N, più un carattere dall'etichetta del bordo che porta a N, è l'infisso più corto di S non trovato in altre stringhe.

Credo che l'etichettatura dei nodi che contengono solo foglie da una stringa possa essere eseguita durante la costruzione o mediante scansione O (N) della GST; quindi è semplice scansionare l'albero finale e mantenere un minimo di esecuzione per ogni stringa. Quindi è tutto O (N).

(Edit - non posso rispondere ai commenti ancora)

Per chiarire, ogni suffisso in un albero suffisso ha un nodo in cui si dirama dalle altre suffissi; l'obiettivo qui è trovare il suffisso/a per ogni stringa che si dirama dai suffissi di tutte le altre stringhe alla profondità minima, misurata dall'etichetta del percorso su quel nodo. Tutto ciò di cui abbiamo bisogno è un carattere extra dopo quel punto per avere una sottostringa che non appare in nessun'altra stringa.

Esempio:

Strings: abbc, abc

Usando l'algoritmo di Ukonnen, dopo la prima stringa che abbiamo un albero suffisso solo i suffissi da quella stringa; Io li etichetta con [1] qui:

abbc[1] 
b 
bc[1] 
c[1] 
c[1] 

successiva inseriamo stringa 2 di suffissi:

ab 
    bc[1] 
    c[2] 
b 
bc[1] 
c 
    [1] 
    [2] 
c 
[1] 
[2] 

Ora vogliamo trovare la stringa più breve che conduce ad un ramo con solo [1] è sotto di esso; possiamo farlo attraverso la scansione tutti i [1] s 'e guardando i loro genitori immediati, che elencherò qui per etichetta percorso, oltre a un carattere (che userò qui di seguito):

abbc: abb 
bbc: bb 
bc: bc[1] 
c: c[1] 

Nota che ho Ho incluso [1] poiché è il metacarattere che distingue i suffissi altrimenti identici di [1] e [2]. Questo è utile quando si identificano sottostringhe che si ripetono in più stringhe, ma non è utile per il nostro problema, poiché se cancelliamo [1] finiamo con una stringa che si verifica anche in [2], cioè non è un candidato.

Ora, nessuna delle etichette a destra si trova in nessun'altra stringa, quindi scegliamo quella più breve che non include un metacarattere, che è bb.

Allo stesso modo, la seconda stringa ha questi candidati:

abc: abc 
bc: bc[2] 
c: c[2] 

Solo uno non ha un metacarattere alla fine, quindi dobbiamo andare con abc.

Il mio punto finale è che questo minimo di ricerca per stringa non deve accadere uno alla volta; la GST può essere scansionata una volta per etichettare i nodi come contenenti foglie da una stringa ([1], [2], .. [n]) o "miste", e quindi le stringhe non condivise minime per stringa (vorrei chiamare questi "distintivi infissi") può essere calcolato anche in un unico passaggio.