辞書/テーブルではなく統計に基づいた「アナグラムソルバー」？

Question

私の問題は、辞書の検索を使用することができないことを除いて、アナグラムの解決に概念的に似ています。私は本当の言葉ではなくもっともらしい言葉を見つけようとしています。

テキストの束の文字に基づいて、n-gramモデル（今のところn = 2）を作成しました。さて、一連の文字のランダムなシーケンスを考えると、遷移確率に応じて最も可能性の高いシーケンスにそれらを透合ヌにしたいと思います。私は必要だと思った viterbiアルゴリズム 私がこれを始めたとき、私がより深く見えると、ViterBiアルゴリズムは、観測された出力に基づいて一連の隠されたランダム変数を最適化します。出力シーケンスを最適化しようとしています。

これについてよく知られているアルゴリズムはありますか？それとも、私はviterbiで正しい軌道に乗っていますか？私はそれを適用する方法を見ていませんか？

アップデート

私はこの問題についてのより多くの洞察を求めるために賞金を追加しました。 （効率的なアプローチが不可能な理由を説明する分析、シミュレートされたアニーリングなどの他のヒューリスティック/近似など）

Answer 1

私があなたの問題を正しく理解している場合、あなたは2グラムの確率の最低製品を持つものの言葉で文字のすべての順列を検索しています。

あなたの言葉がすべての組み合わせを単に強制するには長すぎる場合、確率的最適化アルゴリズムが短時間で良い結果をもたらすことがわかりました。私（数学的背景を持っている）は、アルゴリズムでいくつかの作業を行っています」焼き鈍し法「これはあなたの問題にうまく適合すると思います。そして、実装するのは非常に簡単です。

Answer 2

演習として、私はMATLABにマルコフチェーンの簡単な実装を書きました。基本的に、単語を生成するための文字ベースの確率モデルです。

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

モデルをトレーニングするには、いくつかのテキストが必要です。 Project Gutenbergの「Ozの素晴らしい魔法使い」を使用しています。

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

最後に、モデルを使用して、ランダムワードをサンプリングするか、一連の文字から単語をサンプリングします。

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

「マルコフチェーン」から生成された例が、モデルに与えられた単語のログの設定可能性とともに、多くの例です。

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

正しい言葉ではありませんが、単なるランダムな文字のシーケンスよりも優れていることがわかります。明らかに、前の文字のみを使用して次の文字を生成するだけでは不十分ですが、それでもより洗練されたケース（n-Gram）に簡単に拡張できます。

このようなアプローチの良いところは、1つの言語に限定されておらず、選択した言語からドキュメントを追加するだけで他の言語に適応できることです。

Answer 3

k文字のセットをグラフ内の頂点として考えてください。

各文字からの2グラムを他のすべての文字に表すように指示されたエッジを追加し、それらの確率に対応するウェイトを使用します。

「単語」は、（完全な、指示された）グラフを通るパスです。

あなたは、すべての文字を使用する（すべての頂点にアクセスする）最高の（最小または最も重みのある）「単語」（パス）を探しています。

これは 非対称旅行セールスマンの問題. 。それはnp完全です。 n = 2よりも大きいnグラムを使用すると簡単になるとは思わないので、効率的なアルゴリズムを見つけることはありませんが、そうであればお知らせください

（シミュレートされたアニーリングまたはそれがおそらく行く方法のようなもの）

Answer 4

また、マルコフチェーンでそれを確率的に行うこともできます。手始めに、n-gramテーブルに「単語の始まり」記号が含まれていることを確認してください。次に、その状態から利用可能な遷移を見つけ、それらがあなたのプールからの利用可能な文字のみを含めるようにそれらをフィルタリングし、加重確率を使用してそれらの間でランダムに選択します。次に、からの遷移を見つけます 次 状態、まだ利用可能な文字にろ過し、プールにこれ以上の文字がない場合に終了します（または、移行できない状態に到達した場合は、最初に戻って再試行します）。

あなたは実際にこれが有用であると思うかもしれません もっと 他の利用可能なオプションのいくつかよりもランダムで、それが それも ランダムに、確率をマッサージするか、単にある程度生成するオプションがあります n （100）ランダムな単語の「可能性」で並べ替えて、上部からランダムに選択する m （おそらく10）、文字の袋から生成する単語がより一貫性があるか、よりランダムであるかどうかを比較的うまく制御できます。