logo标签列表

用PHP解密单词的最佳方法是什么？

phpalgorithm
4

我有一个单词列表，想要使用这个单词列表在PHP中解密单词。

似乎PHP没有内置的函数可以实现这一点。所以，有人能否提供一个好的算法来完成这个任务，或者至少指点我正确的方向？

编辑：添加示例

基本上，我说的是我有一个单词列表：

   apple
   banana
   orange

然后，我得到了一堆杂乱无序的字母。
   pplea
   nanaba
   eroang
3
请举一个例子来说明你的意思。 - simshaun
1
你的意思是说你有一个字典（一个正确拼写单词的大列表），你想使用它来将混乱的字母组合成正确的单词。是这样吗？ - Chris Baker
你是在讨论单词中字母的排列组合吗？你打算如何进行匹配？ - Ghpst
7个回答
5
给定一个已知单词的字典：
foreach ($list as $word)
{
  if (count_chars($scrambled_word,1) == count_chars($word,1))
    echo "$word\n";
}

编辑：一个简单的优化是将count_chars($scrambled_word,1)移出循环，因为它从不改变：

$letters = count_chars($scrambled_word,1)
foreach ($list as $word)
{
  if ($letters == count_chars($word,1))
    echo "$word\n";
}
我应该声明，我认为这既不好也不是最好的（就效率而言），但它只是简单易行的。 - Matthew
这很聪明。考虑到单词列表的大小（约10,000个单词），我想这不会对我的运行时间造成太大影响。谢谢。 - rgin
如果您不确定字母大小写，可以考虑添加 strtolower()。 - Xeoncross
Jerry的解决方案比每次扫描更有效。 - Aryabhatta
3
警告：我很少使用PHP，因此这只涉及通用算法，几乎适用于任何语言，而不是PHP特定的内容。
假设您有一个单词，其中字母被重新排列，您想找出可以从这些字母中制作的单词。
如果是这样，一般思路相当简单：复制单词列表，并将每个单词中的字母按字母顺序排序。将每个单词的已排序和未排序版本并排放置，然后按已排序的单词进行排序（但将每个未排序的单词与其已排序的版本保持在一起）。您可能希望将重复项合并在一起，以便（例如）代替{abt:bat}和{abt:tab}，您有：{abt：bat，tab}
然后，要匹配一个混淆的单词，请按字母顺序对其进行排序。在字典中查找匹配项（因为它已排序，所以可以使用二进制搜索）。当您找到匹配项时，结果就是与该排序字母组相关联的单词（或单词）。使用上面的例子，如果混淆的单词是“tba”，则将其排序以获得“abt”，然后查找“abt”以获取“bat”和“tab”。
编辑：正如@Moron在评论中指出的那样，排序和二进制搜索本身并不是关键点。基本要点是将所有等效输入转换为相同的键，然后使用某种快速按键查找单词（们）。
按字母顺序排序每个单词的字母是将等效输入转换为相同键的一种简单方法。对列表进行排序并执行二进制搜索是一种快速查找按键的简单方法。
在这两种情况下，有很多选择。我并不确定这些选择是否会显着提高性能，但它们肯定可以。
例如，您可以不使用纯二进制搜索，而是具有第二级索引，该索引告诉您以“a”开头的键在哪里，以“b”开头的键在哪里，依此类推。鉴于几个极其常用的字母接近字母表的开头（例如“e”和“a”），您可能会更喜欢将单词排序，使得相对不常用的字母（如“q”，“z”等）向键的前面，而最常用的字母位于末尾。这将为基于初始字符的第一个查找提供最大的区别。
在排序/二进制搜索方面，可能有更多的选择，并且可能有更好的理由支持使用其他内容。哈希表通常允许在（几乎）恒定的时间内进行查找。Trie可以大大减少存储空间，特别是当许多单词共享公共前缀时。唯一明显的缺点是，任何一个代码都可能需要更多的工作（尽管PHP的数组类型是基于哈希的，因此您可能可以很好地使用它）。
将单词列表存储在“{abt: bat, tab}”格式中，可能是在效率和工作量平衡方面最好的解决方案。 - Matthew
@konforce：非常正确——如果你经常这样做，你会想要初始化你的字典一次，然后在此之后只需使用它。 - Jerry Coffin
@rgin：根据PHP的（大多数）优点，我可能会使用MySQL（或其他）来处理排序、搜索等部分，并使用PHP读取输入，可能对单个单词进行排序，并针对数据库发出查询。 - Jerry Coffin
不必对整个列表进行排序（并进行后续的二分查找），您可以使用哈希表或Trie（可以节省内存，但编码可能比较复杂）。无论如何加1。 - Aryabhatta
@Jerry：是的，我并不是在找你的答案的错。只是希望你能编辑你的答案，包括那一部分 :-) - Aryabhatta
我留言的唯一原因是为了避免出现近似重复的答案并且不会丢失信息，所以我删除了我的回答并在你的回答下留言。这样做的一个副作用是有可能有用的信息被留在评论中而不是答案中，除非有人编辑它... - Aryabhatta
2

在IT技术中，有一种解密方式可以在O(log p + n)的时间复杂度内完成。

p = size of dictionary 
n = length of word to be unscrambled

假设有一个常数 c ，表示任何单词中某个字母的最多出现次数再加 1。 假设有一个常数 k ，表示字母表中字母的数量。 假设有一个常数 j ，表示可以共享相同哈希值或按字母排序的单词的最大数量。
初始化 O(p) 空间： 1.使用字典D创建一个关联列表按字母排序的单词L，它的大小最多为 p，因为每个单词有一个排序版本。 2.将另一列与L相关联，并用整数的数字哈希值进行关联。哈希值可以在区间[0，c^k-1]内取值。 3.对于L中的每个单词，使用以下函数生成其哈希值：
hash(word) = 0 if word is empty or (c^i + hash(remaining substring of the word))
其中i是第一个字母的零基础字母索引。
算法： 1.在O(n)的时间复杂度下确定问题单词的按字母排序的版本的哈希值h。 2.在O(log p)的时间复杂度下，在L中搜索哈希值。 3.在O(n)的时间复杂度下，列出长度为n的j个相关单词。
理论上，如果你的语言足够稠密，这里的j可能会以O(n!)的速度增长，但我认为这并不适用于已知的口语语言。 - Timothy Swan
0

慢速选项是生成一个乱序单词中所有字母的排列组合，然后通过pspell_check()进行探测。

如果您可以使用原始字典文本文件，则最佳选项是只需使用正则表达式进行扫描：

$dict = file_get_contents("words.txt");  // one word per line

$n = strlen($word);
if (preg_match('/^[$word]{$n}$/im', $dict, $match)) {
    print $match[0];
}

我非常确定PCRE在搜索排列方面比PHP和猜测方法要快得多。

0
利用PHP的数组函数，因为它们可以为您解决此问题。
$words = array('hello', 'food', 'stuff', 'happy', 'fast');
$scrambled_word = 'oehll';

foreach ($words as $word)
{
    // Same length?
    if (strlen($scrambled_word) === strlen($word))
    {
        // Convert to an array and match
        if( ! array_diff(str_split($word), str_split($scrambled_word)))
        {
            print "Your word is: $word";
        }
    }
}

基本上，你要找一个长度相同的东西，然后让PHP来判断所有的字母是否相同。
0
如果您有一个非常大的单词列表，并且希望这个解密操作能够快速完成，我建议将单词列表放入数据库中。接下来，在单词列表表中添加一个字段，该字段是单词的ascii值之和，然后在此ascii值之和上添加索引。
每当您想要检索可能匹配的单词列表时，只需搜索具有与混淆字母的ascii值之和相匹配的ascii值之和的单词表。请记住，您可能会有一些错误匹配，因此您需要比较所有匹配的单词，以确保它们仅包含您混淆的单词的字母（但结果集应该很小）。
如果您不想使用数据库，您可以使用文件实现相同的基本思路，只需按总和值对列表进行排序，以更快地检索所有匹配项。
示例数据假定全部小写（a=97，b=98，c=99，...） bat => 311， cat => 312，...
示例php函数用于计算单词的总和
function asciiSum($word) {
  $characters = str_split(strtolower($word));
  $sum = 0;
  foreach($characters as $character) {
    $sum += ord($character);
  }
  return $sum;
}

更快的方法：向数据库添加另一个字段，表示字符串长度，然后您可以基于ASCII和字符串长度搜索单词，这将进一步减少需要检查的错误匹配数量。
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接