“字谜解算器”的基础上的统计数据，而不是一本词典/表？

StackOverflow https://stackoverflow.com/questions/2650982

题

我的问题是概念上类似于解决字谜，但我不能只用字典查找。我试图找到合理的话，而不是真正的单词。

我已经创建基于在一串文本中的字母一个N元语法模型（现在，N = 2）。现在，由于字母随机序列，我想根据转移概率将其置换成最可能的序列。我以为我会需要 Viterbi算法当我开始这一点，但我看的更深一些，对Viterbi算法优化基于观察到隐藏输出的随机变量的序列。我试图优化输出序列。

有一个著名的算法，这一点，我可以阅读有关？还是我在正确的轨道与维特比对，我只是没有看到如何应用它？

更新

我添加了一个奖金要求更多的洞察这个问题。 （分析解释为什么一个有效的方法是不可能的，其他启发式/除了模拟退火近似值等）

有帮助吗？

解决方案

如果我正确理解你的问题，你正在寻找在一用的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

我们将需要一些文字训练模型。我们使用“绿野仙踪”从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

最后，我们使用该模型来要么样品随机字或词样品从一组字母：

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

下面是一束从字母“markovchains”中产生的例子，给定的模型字的对数概率沿着：

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-克）。

对这种方法的好处是，它不局限于一种语言，并且可以通过简单地从你选择的语言喂养它的文件适用于任何其他。

考虑集合K字母如在图中的顶点。

添加有向边代表2-克从每个信所有其它的，与重量相对应的它们的概率。

一个 “字”，那么，是通过（完全，指导）图形的路径。

您正在寻找最佳（最不或最加权）“字”（路径）使用所有的字母（访问所有顶点）。

这是不对称TSP问题。这是NP完全问题。我不认为这是怎么回事，如果你使用的n-gram比N = 2大，所以你不可能找到一个有效的算法变得更容易，但让我们知道，如果你这样做

（模拟退火或类似的东西可能是要走的路）

您也可以与马尔可夫链做随机。首先，请确保您的N-gram表包括“开头的单词的”符号;然后找到从国家现有的过渡，所以它们进行过滤，他们只包括从池中可用信函，并使用加权的概率当中随机选择。然后找到了的下一步的状态，过滤下来的仍然可用字母，和结束时，有没有更多的字母在游泳池（或者，如果你达到一个状态，你不能过渡的转换出来的，回到开头，然后再试一次）。

您可能实际上会发现它有用，这是的更多的比一些其他可用的选项是随机的，如果它的太的随机你按摩概率的选项，或简单地产生的随机字一些数名词的（例如100），可以通过“似然性”对它们进行排序，然后从顶部之中随机选择的米（也许10），它给你在相对精细控制是否从任何字母袋产生更一致或多个随机词语的

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top