基于统计而非词典/表格的“字谜解答器”？

Question

我的问题在概念上类似于解决字谜游戏，但我不能只使用词典查找。我正在尝试寻找可信的单词而不是实际存在的单词。

我创建了一个基于一些文本中的字母的N-gram模型（现在，N=2）。现在，给定一个随机序列的字母，我想把它们排列成最可能的序列，根据转移概率。我开始时认为需要使用Viterbi算法，但是随着深入研究，我发现Viterbi算法优化了一系列基于观察到的输出的隐藏随机变量的序列。我正在尝试优化输出序列。

是否有一个众所周知的算法，我可以阅读相关信息？或者我正在正确地使用Viterbi算法，只是没有看到如何应用它？

更新

我添加了奖励以获得更多关于这个问题的见解。（分析说明为什么不可能有有效的方法，除了模拟退火之外的其他启发式/近似算法等）

- user132748

---

我明白了，你正在制作一个自动诅咒生成器：http://thedailywtf.com/Articles/The-Automated-Curse-Generator.aspx ;) - Guffa

请注意，过滤器永远不够用。你写的任何东西在某个人的解释中都会是令人印象深刻的亵渎之词。 - Yann Vernier

Answer 1

作为一项练习，我用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

我们需要一些文本来训练模型。我们使用古腾堡计划中的《绿野仙踪》。

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

这里提供了一些由“Markov Chains”字母生成的示例，以及模型给出的单词对数概率：

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元语法）。

这种方法的好处在于它不限于一种语言，并且可以通过提供来自你选择的语言的文档来适应任何其他语言。

- Amro

Answer 2

考虑将K个字母看作图中的顶点。

添加有向边以表示每个字母到其他所有字母的2-gram，并赋予其对应的概率权重。

那么，一个“单词”就是通过（完整的、有向的）图的路径。

您要寻找使用所有字母（访问所有顶点）的最佳（最小或最大加权）“单词”（路径）。

这是非对称旅行商问题。它是NP完全的。我认为如果您使用大于N=2的N-gram，情况不会变得更容易，因此您不太可能找到有效的算法，但如果您找到了，请告诉我们。

（模拟退火或类似方法可能是解决该问题的途径）。

- Zac Thompson

Answer 3

如果我正确理解您的问题，您正在搜索单词中所有字母的排列，以找到2-gram概率最低的一个。

如果您的单词太长以至于无法暴力尝试所有组合，我发现随机优化算法可以在短时间内产生良好的结果。我（具有数学背景）已经对“模拟退火”算法进行了一些工作，我认为它非常适合您的问题。而且实现起来相当容易。

- Jens

Answer 4

你也可以使用马尔可夫链来进行随机生成。首先，确保你的N-gram表格包括一个“单词开头”的符号；然后找到从该状态可用的转换，并过滤它们，使它们只包括来自你的池中可用的字母，并使用加权概率在它们之间随机选择。然后找到从下一个状态的转换，缩小到仍然可用的字母，并在池中没有更多字母时结束（或者，如果你到达一个无法转换出去的状态，则返回到开头并重试）。

你可能会发现这比其他可用选项更加随机，如果它太随机了，你可以调整概率，或者简单地生成一些数字n（比如100）个随机单词，按它们的“可能性”排序，然后从前m（也许是10）个中随机选择，这样你就可以相对精细地控制从任何字母袋中生成的单词是更一致还是更随机。

- hobbs