Algoritmo per rilevare se un elenco di stringhe ha bisogno di delimitatori

Question

Algoritmo per rilevare se un elenco di stringhe ha bisogno di delimitatori

#1 da (2 voti)
#2 da (1 voti)

1

Ho bisogno di scrivere una funzione per rilevare se un insieme di stringhe ha bisogno di delimitatori se concatenato in qualsiasi ordine.

Ad esempio, le stringhe ("A","B","C") non hanno bisogno di un delimitatore: "ABCBB" -> ["A","B","C","B","B"] .

Tuttavia, le stringhe ("Pop","corn","Popcorn") do hanno bisogno di un delimitatore, poiché la stringa "Popcorn" è ambigua: può essere ["Pop","corn"] o ["Popcorn"] .

Altri due casi:

("Pop","Popcorn","Kernel") -> Not ambiguous
("A","AB","BC","BA") -> Ambiguous (on the string "ABCA")

Algoritmi che ho preso in considerazione, ma non funzionano:

Verifica se una stringa inizia con un'altra stringa, che non riesce ("Pop","Popcorn","Kernel")
Verifica se una stringa è completamente composta da altre stringhe, che non riesce ("A","AB","BC","BA")
Test di tutte le possibili combinazioni di stringhe (non riesce a terminare in modo non ambiguo)

Come posso rilevare (si spera in modo efficiente) se un insieme di stringhe ha bisogno di un delimitatore quando è concatenato?

algorithms

posta Nathan Merrill 19.02.2016 - 17:01

fonte

2 risposte

1

Penso che la struttura che stai cercando sia un 'Trie' comunemente usato per il completamento automatico, il controllo ortografico ecc.

Nel tuo caso un trie che è piatto, cioè nessun nodo ha un nodo figlio, dovrebbe equivalere a nessuna delle parole che sono una sottostringa all'inizio di una qualsiasi delle altre e quindi la tua capacità di omettere un delimitatore.

Nel caso di 'pop' e 'popcorn' ma non 'mais' è necessario controllare entrambi i nodi duplicati nel trie. E nodi che non sono parole

Cioè ho pop- > mais ma solo una istanza di ciascun

dove come se aggiungessi la parola "orn" avrei root - > pop- > c- > orn e root- > orn, ma un nodo non parola 'c'

Se aggiungo "mais" ho root- > pop- > mais e root- > mais. Con no non parole

Hmmm non ci penso forse ...

risposta data 19.02.2016 - 18:56

fonte

Leggi altre domande sui tag algorithms

Best practice per la creazione di versioni definite in git Domanda di implementazione .NET (accesso al repository)

score 2 · Accepted Answer

Dopo aver riflettuto, c'è un semplice algoritmo.

Supponi di avere due stringhe xey, e nessuno dei due è un prefisso dell'altro. Nulla di ciò che potresti aggiungere loro li renderebbe uguali, quindi non sono di alcun interesse. Ciò che ti interessa sono le stringhe x e xa, dove xa non è stato creato aggiungendo stringhe a x: potremmo essere in grado di aggiungere parole dalla tua lista ad entrambi xe xa e ottenere le stesse due stringhe. In realtà, ci interessa solo a.

Sia L la tua lista. Creiamo un set S di tutte le stringhe in modo tale che per alcune x, sia x che xa possano essere formate da parole nel tuo elenco, senza creare xa aggiungendo parole a x. Ma L non contiene alcun prefisso di "mais" e nessuna parola che inizia con "mais", quindi abbiamo finito e L è univoco.

Inizialmente S è vuoto. Controlliamo tutte le coppie (x, y) di stringhe in L. Se x è vuoto o x = y allora L è ambiguo. Altrimenti se y = xa o x = ya allora aggiungi un al set S. (Nel tuo ultimo esempio, le due stringhe A e AB nella tua lista aggiungono "B" all'insieme S).

Quindi per ogni stringa x in S, e per ogni stringa y in L: Se x = y, allora L è ambiguo. Altrimenti se y = xa o x = ya allora aggiungi un al set S. Ripeti finchè nient'altro può essere aggiunto a S; in tal caso L è univoco.

Nel tuo ultimo esempio, S contiene "B". Poiché L contiene "BC" e "BA", aggiungiamo "C" e "A". "C" non ci lascia nulla perché nessuna stringa in L inizia con "C". Ma "A" è in realtà un elemento di L, che rende L ambiguo.

Il tuo primo esempio non è ambiguo perché né "A", "B", "C" è il prefisso di un altro.

Nel tuo secondo esempio, poiché L contiene "Pop" e "Popcorn", aggiungi "mais" a S. E "mais" è un elemento di S, quindi è ambiguo. Nel tuo terzo esempio, aggiungiamo anche "mais" a S, ma L non contiene alcun prefisso di "mais" e nessuna stringa che inizia con "mais", quindi abbiamo finito e L è univoco.