« Solveur Anagram » basé sur les statistiques plutôt qu'un dictionnaire / table?

Question

Mon problème est conceptuellement similaire à la résolution anagrammes, sauf que je ne peux pas utiliser une recherche dans le dictionnaire. Je suis en train de trouver des mots plausibles plutôt que de vrais mots.

J'ai créé un modèle N-gramme (pour l'instant, N = 2) sur la base des lettres dans un tas de texte. Maintenant, étant donné une séquence aléatoire de lettres, je voudrais les permute dans la séquence la plus probable selon les probabilités de transition. Je pensais que je aurais besoin algorithme de Viterbi quand j'ai commencé, mais comme je regarde plus profondément, la algorithme de Viterbi permet d'optimiser une séquence de variables aléatoires cachées sur la base de la sortie observée. Je suis en train d'optimiser la séquence de sortie.

Y at-il un algorithme bien connu pour ce que je peux lire? Ou suis-je sur la bonne voie avec Viterbi et je suis tout simplement pas voir comment l'appliquer?

Mise à jour

J'ai ajouté une prime de demander une meilleure idée de ce problème. (Analyse expliquant pourquoi une approche efficace est impossible, d'autres heuristiques / approximations en plus de recuit simulé, etc.)

Answer 1

Si je comprends votre problème correctement, vous êtes à la recherche toutes les permutations de lettres dans un mot pour celui qui produit le plus faible des probabilités 2 grammes.

Si votre mot est trop long à la force brute simplement toutes les combinaisons, j'ai trouvé que les algorithmes d'optimisation stochastique produisent de bons résultats en peu de temps. I (ayant un fond mathématique) ont fait un travail sur l'algorithme « Recuit Simulé », qui Je pense cadrerait bien à votre problème. Et il est assez facile à mettre en œuvre.

Answer 2

En guise d'exercice, je l'ai écrit une implémentation simple des chaînes de Markov en Matlab. Fondamentalement, son modèle probabiliste basé lettre aux mots de génération.

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

Nous aurons besoin du texte pour former le modèle. Nous utilisons 'Le Magicien d'Oz' de 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

Enfin, nous utilisons le modèle à deux échantillons aléatoires mots ou des mots échantillons d'un ensemble de lettres:

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

Voici un tas d'exemples générés à partir des lettres de markovchains ', ainsi que log-probabilité du mot donné le modèle:

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

Vous pouvez voir que même si aucun sont bons mots, ils sont encore mieux qu'une séquence aléatoire de lettres. De toute évidence, en utilisant uniquement le caractère précédent pour générer la suivante ne suffit pas, encore il peut être facilement étendu à des cas plus sophistiqués (N-gramme).

La bonne chose au sujet d'une telle approche est que ne se limite pas à une seule langue, et peut être adapté à tout autre simplement nourrir les documents de langue de votre choix.

Answer 3

Considérons l'ensemble de lettres K comme sommets dans un graphe.

Ajouter bords dirigé pour représenter les 2-grammes de chaque lettre à tous les autres, avec des poids qui correspondent à leurs probabilités.

A "mot" est donc un chemin à travers le graphe (complet, dirigée).

Vous cherchez le meilleur (ou moins avancés plus pondérée) « mot » (chemin) qui utilise toutes les lettres (visites tous les sommets).

Ceci est Voyager asymétrique Salesman problème . Il est NP-complet. Je ne pense pas que ça va être plus facile si vous utilisez N-grammes plus grand que N = 2, de sorte que vous êtes de ne pas trouver probablement un algorithme efficace, mais laissez-nous savoir si vous faites

(Recuit Simulé ou quelque chose comme il est sans doute la voie à suivre)

Answer 4

Vous pouvez aussi le faire avec une chaîne stochastiquement Markov. Pour commencer, assurez-vous que votre table N-gramme comprend un symbole « début de mot »; puis trouver les transitions disponibles à partir de cet état, et les filtrer afin qu'ils ne comprennent que les lettres disponibles à partir de votre piscine, et choisir au hasard parmi les probabilités pondérées à l'aide. Ensuite, trouver les transitions de la suivant état, filtrage vers le bas aux lettres encore disponibles, et à la fin quand il n'y a plus de lettres dans la piscine (ou, si vous atteignez un état que vous ne pouvez pas la transition sur, revenir au début et essayez à nouveau).

Vous pouvez effectivement trouver utile que cela est plus au hasard que certains des autres options disponibles, et si elle est aussi au hasard, vous avez la possibilité de massage des probabilités, ou simplement générer un nombre n (par exemple 100) des mots au hasard, de les trier par leur "probabilité", puis en choisissant au hasard parmi les top m (peut-être 10), ce qui vous donne un contrôle relativement bien de savoir si les mots que vous générez de tout sac de lettres sont plus cohérents ou plus aléatoire.