3

我有一段文本被两个字符的列打乱。我的任务的目的是解读它：

|de|  | f|Cl|nf|ed|au| i|ti|  |ma|ha|or|nn|ou| S|on|nd|on|
|ry|  |is|th|is| b|eo|as|  |  |f |wh| o|ic| t|, |  |he|h |
|ab|  |la|pr|od|ge|ob| m|an|  |s |is|el|ti|ng|il|d |ua|c |
|he|  |ea|of|ho| m| t|et|ha|  | t|od|ds|e |ki| c|t |ng|br|
|wo|m,|to|yo|hi|ve|u | t|ob|  |pr|d |s |us| s|ul|le|ol|e |
| t|ca| t|wi| M|d |th|"A|ma|l |he| p|at|ap|it|he|ti|le|er|
|ry|d |un|Th|" |io|eo|n,|is|  |bl|f |pu|Co|ic| o|he|at|mm|
|hi|  |  |in|  |  | t|  |  |  |  |ye|  |ar|  |s |  |  |. |

我目前查找正确列顺序的方法是尝试根据单词出现计数标准递归地找到每列的最佳位置。

我想到的算法核心的伪代码是：

function unscramble(scrambledMatrix,indexOfColumnIveJustMoved)
    for each column on scrambledMatrix as currentIndex=>currentColumn
       if (currentIndex!=indexOfColumnIveJustMoved)
           maxRepeatedWords=0;maxIndex=0;
           for (i=0;i<numberOfColumnsOfScrambledMatrix;i++)
              repWordsCount=countRepWords(moveFromToOn(currentIndex,i,scrambledMatrix))
              if (maxRepeatedWords<repWordsCount)
                  maxRepeatedWords=repWordsCount;
                  maxIndex=i;
              endif
           endfor
           if (maxIndex!=currentIndex)
               return unscramble(moveFromToOn(currentIndex,maxIndex,scrambledMatrix),maxIndex); //recursive call
           endif
       endif
    endfor
    return(scrambledMatrix); //returns the unscrambled matrix;
endfunction

当对每一列进行迭代后没有移动列时，算法停止。我猜它应该适用于任何语言（尽管我只对英语的解决方案感兴趣）只要写作是基于由字母组成的单词并且样本足够大。

关于任何其他方法或改进的任何建议？我想知道这个问题的最佳解决方案（可能是基于字典的字典来寻找常见单词的出现？重建算法以避免递归，会更快吗？）。

4

1 回答 1

1

还有一些想法：

  • 引号，对于每个打开的引号，后面必须有一个结束引号。
  • 大写字母，通常是句子或名词等的开头（适用的任何附加语法规则
  • 使用足够小的字典以适应所有内存，并计算特定排列中有效单词的数量。

一种方法，尽管通常这种方法是最耗时的方法之一——是使用遗传算法。

可以说当前的默认列排列是

|de|  | f|Cl|nf|ed|au| i|ti|  |ma|ha|or|nn|ou| S|on|nd|on|
[0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18] <--- define this to be a chromosome

您可以创建一个由 100、1000 w/e 数量的染色体组成的种群，这些染色体从随机分配开始（请记住，“随机”分配不能有重复的数字，并且必须是有效的）

然后对每个任务运行一个适应度函数，或者如果你想以这种方式分解它，可以运行多个适应度函数。从一个超级适应度函数开始，它为每个分配分配一个适应度值。

只取前 50% 的染色体并将它们转移到下一代，根据您选择的交叉函数和突变概率创建“子”染色体——对于这类问题，我建议使用非常轻的交叉函数（或没有...）和不错的突变率。如果您能找到对单词/适应度函数贡献不大的列，那么可能会翻转它们。

继续这样做很多代，看看每一代评价最高的作业是什么样子的，你会期望有效值在某个时候达到稳定，这将是你正确的作业。

这种方法只能比具有适应功能的蛮力稍微好一点，但结果也可能相当不错。

最后一个想法：尝试从“第一列，第二列”中抽象出来，并将这些列分配为构成单词的块，因为仅仅因为 [1,4,6....] 最终形成了“the”“him” “她”等，并不意味着它一开始就属于。

我有一种我更喜欢的不同方法，我认为动态算法更适合于此。

编辑：另一种方法

再次基于字典方法，但您将专注于在其余列之前选择前几列，如果它分崩离析并且您没有在任何特定行中获取单词，则意味着您之前的选择是错误的，您将需要回溯。

选择第 1 行 .. 很可能这里没有太多单词，但您会将自己缩小到字典的子集 - 包含以第一列中的字符开头的单词的子集。

现在您有一行可以使用，请选择右侧的相邻行。如果它要么形成完整的单词，要么仍然有可能的有效单词（假设没有空格表示单词的结尾）。重复。

如果您之前的选择没有相邻的行，请向左回溯一行，并且不要再次选择相同的内容。

这里的弱点是您的字典需要包含句子中的所有单词以及单词的所有变体。你可能需要想出一个类似于适应度函数的启发式方法，“90% 的单词匹配，所以这仍然是一个有效的尝试......”或类似的东西。

于 2012-02-22T23:30:08.343 回答