“Anagram solver” sulla base di statistiche piuttosto che un dizionario / tavolo?

Question

Il mio problema è concettualmente simile a anagrammi solving, tranne che non può semplicemente utilizzare una ricerca dizionario. Sto cercando di trovare le parole plausibili, piuttosto che le parole reali.

Ho creato un modello N-gram (per ora, N = 2) sulla base delle lettere in un gruppo di testo. Ora, data una sequenza casuale di lettere, vorrei li permutare nella sequenza più probabile in base alle probabilità di transizione. Ho pensato che avrei avuto bisogno della algoritmo di Viterbi quando ho iniziato questo, ma mentre guardo più in profondità, il Viterbi algoritmo ottimizza una sequenza di variabili casuali nascoste basate sull'uscita osservato. Sto cercando di ottimizzare la sequenza di uscita.

C'è un algoritmo ben noto per questo che posso leggere? O sono sulla strada giusta con Viterbi e non sto solo vedendo come applicarla?

Aggiorna

ho aggiunto una taglia per chiedere informazioni più dettagliate su questo problema. (Analisi spiegando il motivo per cui un approccio efficiente non è possibile, altre euristiche / approssimazioni oltre ricottura simulata, ecc.)

Answer 1

Se ho capito bene il problema, si sta cercando tutte le permutazioni delle lettere in una parola per quello con il prodotto più basso delle probabilità 2 grammi.

Se la parola è troppo lungo per la forza bruta semplicemente tutte le combinazioni, ho trovato che gli algoritmi di ottimizzazione stocastici producono buoni risultati in breve tempo. I (avendo un background matematico) ho fatto un po 'di lavoro sulla algoritmo " Simulated Annealing ", che credo che si adatterebbe bene al vostro problema. Ed è abbastanza facile da implementare.

Answer 2

Come esercizio, ho scritto una semplice implementazione delle Catene di Markov in MATLAB. Fondamentalmente il suo un modello probabilistico lettera-based per parole generatrici.

function mc = MC(numStates)
    N = numStates;
    PI = ones(1,N)/N;
    TR = ones(N,N)/N;
    mc = struct('logprob',@logprob, 'train',@train, ...
                'sample',@sample, 'sampleFiltered',@sampleFiltered);

    function train(seqs)
        PI = 1 + histc(cellfun(@(c)c(1), seqs)', 1:N); %#'
        TR = ones(N,N);
        for i=1:numel(seqs)
            ind = sub2ind([N N], seqs{i}(1:end-1), seqs{i}(2:end));
            TR = TR + reshape(histc(ind,1:N*N), [N N]);
        end
        PI = bsxfun(@rdivide, PI, sum(PI,2)+(sum(PI,2)==0));
        TR = bsxfun(@rdivide, TR, sum(TR,2)+(sum(TR,2)==0));
    end

    function seq = sample(len)
        seq = zeros(1,len);
        seq(1) = randsample(1:N, 1, true, PI);
        for t=2:len
            seq(t) = randsample(1:N, 1, true, TR(seq(t-1),:));
        end
    end

    function seq = sampleFiltered(allowed)
        len = numel(allowed);
        seq = zeros(1,len);
        seq(1) = randsample(allowed, 1, true, PI(allowed));
        allowed( find(allowed==seq(1),1,'first') ) = [];
        for t=2:len-1
            seq(t) = randsample(allowed, 1, true, TR(seq(t-1),allowed));
            allowed( find(allowed==seq(t),1,'first') ) = [];
        end
        seq(t) = allowed;
        seq = seq(seq~=0);
    end

    function LL = logprob(seq)
        LL = log(PI(seq(1))) + ...
             sum( log(TR(sub2ind([N N],seq(1:end-1),seq(2:end)))) );
    end
end

Ci sarà bisogno del testo per il training del modello. Usiamo 'Il meraviglioso mago di Oz' da Project Gutenberg.

%# read the text document
str = lower( urlread('http://www.gutenberg.org/files/55/55.txt') );
SP = char(32);                        %# delimiter (space)
str( ~isstrprop(str, 'alpha') ) = SP; %# replace non-letters with spaces
str( findstr(str, [SP SP]) ) = [];    %# consecutive spaces as one
idx = ( str == SP );                  %# location of spaces
df = diff([1 idx 1]);
len = find(df > 0) - find(df < 0);    %# length of each word
[seqs gn] = grp2idx( str(~idx)' );    %#' map letters to numbers starting from 1
seqs = mat2cell(seqs', 1, len)';      %# put each word in a separate cell
N = length(gn);                       %# A to Z

Infine, usiamo il modello di parole a caso sia di esempio o le parole di esempio da un insieme di lettere:

%# train Markov chain
mc = MC(N);
mc.train(seqs);

%# sample a random word
seq = mc.sample( randi([3 10]) );
fprintf('word = %s , logP(word)=%f\n', [gn{seq}], mc.logprob(seq))

%# sample a word from a set of letters
letters = lower('markovchains');
lettersIdx = cellfun(@(c) find(strcmp(c,gn)), cellstr(letters'));   %#'
seq = mc.sampleFiltered(lettersIdx);
fprintf('word = %s , logP(word)=%f\n', [gn{seq}], mc.logprob(seq))

Ecco un mucchio di esempi generati da 'markovchains' le lettere, insieme con log-probabilità della parola dato il modello:

word = mivorancask , logP(word)=-29.610819
word = arknoamshiv , logP(word)=-32.496090
word = ancoramshik , logP(word)=-29.299897
word = orchisankav , logP(word)=-29.987204
word = avinchasorm , logP(word)=-27.178507
word = aronchaskim , logP(word)=-25.651964

Si può vedere che, anche se nessuno è parole corrette, sono ancora meglio di solo una sequenza casuale di lettere. Ovviamente utilizzando solo il carattere precedente per generare il prossimo non è sufficiente, ancora può essere facilmente esteso a casi più sofisticati (N-gram).

La cosa bella di questo approccio è che non è limitato a una lingua, e può essere adattato a qualsiasi altro semplicemente alimentandola documenti dalla lingua di propria scelta.

Answer 3

Si consideri l'insieme di lettere K come vertici in un grafo.

blog bordi diretta a rappresentare i 2-grammi di ciascuna lettera a tutte le altre, con pesi che corrispondono alle loro probabilità.

A "parola", quindi, è un percorso attraverso la (diretto completo) grafico.

Stai cercando il miglior "parola" (dei minimi o quasi-ponderata) (percorso) che utilizza tutte le lettere (visite tutti i vertici).

Questo è il asimmetrica problema del commesso viaggiatore . E 'NP-completo. Non credo che sta andando a diventare più semplice se si utilizza N-grammi più grande di N = 2, in modo da non siete suscettibili di trovare un algoritmo efficiente, ma di farci sapere se si fa

(Simulated Annealing o qualcosa di simile è probabilmente la strada da percorrere)

Answer 4

Si potrebbe anche farlo stocasticamente con una catena di Markov. Per cominciare, assicuratevi che il vostro tavolo N-gram include un simbolo "all'inizio della parola"; poi trovare le transizioni disponibili da quello stato, e filtrare in modo che essi comprendono solo le lettere disponibili dalla vostra piscina, e scegliere a caso tra di loro utilizzando le probabilità ponderata. Poi trovare le transizioni dalla Avanti Stato, filtrando verso il basso per le lettere ancora disponibili, e alla fine quando non ci sono più lettere in piscina (o, se si raggiunge uno stato che non è possibile transizione fuori, tornare all'inizio e provare di nuovo).

Si può effettivamente essere utile che questo è più casuale rispetto ad alcune delle altre opzioni disponibili, e se è anche a caso si ha la possibilità di massaggiare le probabilità, o semplicemente generando un certo numero n (esempio 100) di parole a caso, ordinandoli per loro "rischio", e quindi scegliendo casualmente tra i top m (forse 10), che ti dà il controllo relativamente fine sopra se le parole generate da qualsiasi borsa di lettere sono più coerenti e più casuale.