基于统计学而不是字典/表的“Anagram求解器”？

Question

我的问题是在概念上类似于解决anagrams，除了我不能只使用字典查找。我试图寻找合情合理的单词而不是真实的单词。

我已经创建了一个N元语法模型（现在，N = 2）的基础上在一堆文本的字母。现在，给定一个随机的字母序列，我想根据转换概率将它们排列成最可能的序列。当我开始时，我认为我需要Viterbi algorithm，但当我看起来更深时，维特比算法会根据观察到的输出优化一系列隐藏的随机变量。我正在尝试优化输出顺序。

是否有一个众所周知的算法，我可以阅读？还是我在维特比的正确轨道上，我只是没有看到如何应用它？

更新

我添加了一个赏金来要求更深入了解这个问题。 （分析解释了为什么不可能使用有效的方法，其他启发式/近似，除了模拟退火等）

Answer 1

如果我正确理解您的问题，您正在搜索字母中所有字母的排列组合2克概率的乘积。

如果你的话太长，干脆蛮力所有组合，我发现，随机优化算法产生在很短的时间了良好的效果。我（有一个数学背景）已经在算法“Simulated Annealing”上做了一些工作，我认为这很适合你的问题。而且实现起来很容易。

Answer 2

考虑一组K字母作为图中的顶点。

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

然后，“单词”是通过（完整，有向）图的路径。

您正在寻找最好的（最不或大部分权重）使用所有的字母（访问所有顶点）“字”（路径）。

这是asymmetric Traveling Salesman Problem。这是NP完整的。如果你使用大于N = 2的N-grams，我认为它不会变得更容易，所以你不可能找到一个有效的算法，但是让我们知道你是否做了

（模拟退火或其他喜欢它可能是要走你也可以用马尔可夫链做随机的方式）

Answer 3

。对于初学者来说，确保你的N-gram表包含一个“词的开头”符号;然后从该状态中找到可用的转换，并对它们进行过滤，以便它们只包含来自池中的可用字母，并使用加权概率随机选择它们。然后找到下一个状态的转换，过滤到仍然可用的字母，并在池中没有更多字母时结束（或者，如果您达到不能转换的状态，请返回到一开始，然后再试一次）。

你实际上可能会发现它有用，这比一些其他的可用选项随机更，如果它是太随机你按摩的概率，或只是产生一些数量ñ的选项（说100）随机词，排序他们的“可能性”，然后从顶部m（也许10）中随机选择，它可以相对很好地控制你是否从任何信件包生成的单词更多一致或更随机。

Answer 4

作为练习，我在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-gram）。

这种方法的好处在于它不仅限于一种语言，而且可以通过简单地从您选择的语言中提供文档来适应任何其他语言。