„Anagramm lösen“, basierend auf Statistiken eher als ein Wörterbuch / table?

Question

Mein Problem ist zu lösen Anagramme vom Konzept her ähnlich, außer ich nicht nur einen Wörterbuch-Lookup verwenden kann. Ich versuche, plausible Worte eher als echte Worte zu finden.

Ich habe ein N-Gramm-Modell erstellt (für jetzt, N = 2), bezogen auf den Buchstaben in einer Reihe von Text. Nun, da eine zufällige Folge von Buchstaben, ich mag sie in die wahrscheinlichste Folge permutieren nach den Übergangswahrscheinlichkeiten. Ich dachte, ich müsste die Viterbi-Algorithmus wenn ich dies begonnen, aber wie ich sehe tiefer, die Viterbi-Algorithmus optimiert eine Sequenz von versteckten Zufallsvariablen basierend auf der beobachteten Ausgabe. Ich versuche, die Ausgangssequenz zu optimieren.

Sie haben einen bekannten Algorithmus dafür, dass ich lesen können? Oder bin ich auf dem richtigen Weg mit Viterbi und ich bin einfach nicht sehen, wie es anzuwenden?

Update

Ich habe eine Prämie hinzugefügt, um einen besseren Einblick in dieses Problem zu stellen. (Analyse zu erklären, warum ein effizienter Ansatz nicht möglich ist, andere Heuristik / Annäherungen neben simuliertem Glühen usw.)

Answer 1

Wenn ich Ihr Problem richtig verstehe, sind Sie alle Permutationen von Buchstaben in einem Wort für den mit dem niedrigsten Produkt von 2-Gramm-Wahrscheinlichkeiten zu suchen.

Wenn Ihr Wort zu lang ist, alle Kombinationen zu einfach Brute-Force, ich habe festgestellt, dass stochastische Optimierungsalgorithmen gute Ergebnisse in kurzer Zeit produzieren. I (einen mathematischen Hintergrund hat) hat einige Arbeit auf dem Algorithmus getan „ simuliertes Ausglühen “, die ich denke, wäre schön, um Ihr Problem zu passen. Und es ist ziemlich einfach zu implementieren.

Answer 2

Als Übung, schrieb ich eine einfache Implementierung von Markov-Ketten in MATLAB. Im Grunde ist es ein Schreiben auf Wahrscheinlichkeitsmodell zu generierenden Worten.

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

Wir werden einen Text müssen das Modell zu trainieren. Wir verwenden ‚Der Zauberer von Oz‘ von 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

Schließlich verwenden wir das Modell entweder Probe zufällige Wörter oder Beispielwörter aus einer Reihe von Buchstaben:

%# 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))

Hier ist eine Reihe von Beispielen aus den Buchstaben ‚markovchains‘ erzeugt, zusammen mit log-Wahrscheinlichkeit des Wortes des Modell gegeben:

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

Sie sehen, dass obwohl keine richtigen Worte sind, sind sie noch besser als nur eine zufällige Folge von Buchstaben. Offensichtlich nur mit dem vorherigen Zeichen der nächsten zu erzeugen nicht genug ist, kann es immer noch leicht zu anspruchsvollere Fälle ausgedehnt werden (N-Gramm).

Das Schöne an einem solchen Ansatz ist, dass es nicht auf eine Sprache beschränkt und kann einfach auf andere angepasst werden, indem es Dokumente aus der Sprache Ihrer Wahl Fütterung.

Answer 3

Wir betrachten die Menge von K Buchstaben als Eckpunkte in einem Diagramm.

gerichteten Kanten Fügen Sie die 2-Gramm von jedem Brief an alle die anderen zu repräsentieren, mit Gewichten, dass entsprechen deren Wahrscheinlichkeiten.

ein "Wort" ist, dann wird ein Pfad durch die (vollständig, gerichtet) -Darstellung.

Sie suchen nach den besten (am wenigsten oder am meisten gewichtet) „Wort“ (Pfad), der verwendet alle die Buchstaben (Besuche alle Ecken).

Dies ist das asymmetrische Reisen Salesman Problem . Es ist NP-vollständig. Ich glaube nicht, es wird einfacher, wenn Sie verwenden N-Gramm größer als N = 2, so dass Sie wahrscheinlich nicht einen effizienten Algorithmus zu finden, aber lassen Sie uns wissen, wenn Sie tun

(simuliertes Ausglühen oder so etwas wie es ist wahrscheinlich der Weg zu gehen)

Answer 4

Sie können es auch mit einer Markov-Kette tun stochastisch. Für den Anfang, stellen Sie sicher, dass Ihre N-Gramm-Tabelle ein „Anfang des Wortes“ Symbol enthält; findet dann die verfügbaren Übergänge von diesem Zustand und filtern, so dass sie nur Briefe von Ihrem Pool, und wählt zufällig unter ihnen gewichteten Wahrscheinlichkeiten. Dann findet die Übergänge von dem weiter Zustand, Filterung auf die noch verfügbaren Buchstaben nach unten, und am Ende, wenn es keine weiteren Buchstaben im Pool sind (oder, wenn man einen Zustand erreichen, dass man nicht Übergang aus, gehen Sie an den Anfang zurück und versuchen Sie es erneut).

Sie können tatsächlich finden es sinnvoll, dass dies mehr zufällig als einige der anderen verfügbaren Optionen, und wenn es zu zufällig haben Sie die Möglichkeit, die Wahrscheinlichkeiten der Massage, oder einfach nur ein bestimmte Anzahl zu erzeugen n (zB 100) von zufälligen Worten, sie durch ihre "Wahrscheinlichkeit" Sortieren und dann zufällig aus dem Top-Auswahl m (vielleicht 10), was Sie relativ feine Kontrolle darüber, ob die Worte, die Sie von jedem Sack Buchstaben erzeugen, sind konsistentere oder mehr zufällig.