14

我正在尝试创建一个算法来建议Mad Gab风格的短语。

输入是一组短语。我还有一组关键字，我想尽可能使用它们。目前，我的解决方案只是蛮力：

  • 循环短语（逐个字符）
    • 如果找到关键字
      • 存储关键字和分支（递归）
    • 增加字符数

但是，我遇到的问题是：

  • 考虑复合关键字，例如“catchs”可以是“catches”、“cat”+“cheeses”
  • 允许字面意思 - “the”、“and”、“one”、“two”、“three”。
  • 如何建议不是关键字的术语。即，当找不到关键字或文字时，求助于系统字典之类的东西。
  • 跳过短语片段。现在它只是通过一次。但是考虑一下短语以不匹配的内容开头但后面几个字符包含匹配项的情况。

我最熟悉 PHP 和 MySQL。但是，如果它提供更好的解决方案，我对另一种技术持开放态度。

我也对任何其他建议感兴趣。特别是使用第二个参数的方法metaphone()来提出更难的建议。

4

2 回答 2

6

也许从短语库上的音节划分算法开始。您甚至可以使用教孩子划分音节的简单资源来创建粗略的划分方法：

http://www.ewsdonline.org/education/components/scrapbook/default.php?sectiondetailid=7584

如果您想要一种更技术、更准确的方法，那么有一个博士学位。关于如何做的论文：

http://www.tug.org/docs/liang/

然后使用您自己滚动的内容或 metaphone() 将每个音节转换为语音表示。您可以使用解释元音发音规则的类似网站。这些只是概括。如果您自己滚动，您将处理元音与辅音分开。Metaphone 只使用辅音，这很好，但不如你还考虑元音那么酷。

元音： http://www.eslgold.com/pronunciation/english_vowel_sounds.html 辅音： http ://usefulenglish.ru/phonetics/english-consonant-sounds

然后，您的单词库中有一本英语单词词典。有许多可用的开源字典，您可以将它们粘贴到 MySQL 表中。

从第一个音节开始，在字典中查找与 soundex 测试匹配的随机单词。如果你找不到一个（这通常只会找到一个音节词）添加额外的音节并再次搜索。

例子：

“逻辑后果”

A. 音节分割

“逻辑后果”

B. 应用元音

“lah gee cahl con see quince”

C. 应用辅音

"lah jee kahl kon see quinse"

D. Soundtext 测试（一个音节 soundex - 显然太容易猜到，但它证明了这个概念）

“Law Gee Call Con Sea Quints”

Soundex strcmp 的返回一个数字。因此，如果您愿意，您可以提前获取单词库中所有内容的 soundex 值。然后你可以快速运行strcmp。

Soundex MySQL 比较的一个示例是：

选择 strcmp(soundex('lah'), soundex('law'));

如果您想从大型数据库中获取随机结果并且您已经在字典表的字段中捕获了 soundex 值，我认为使用 MySQL soundex 比 PHP soundex 测试更容易。

我的建议可能效率低下，但优化是一个不同的问题。

更新：

我并不是要暗示我的解决方案只会产生一个音节词。我以一个音节为例，但如果你把两个音节放在一起，你会得到多音节匹配。实际上，您可能只是从将所有音节组合在一起并在 mysql 中运行 soundex 开始。如果您找到答案，那就太好了。但是随后您可以滚动音节，直到获得最长的匹配。然后你就剩下短语的结尾了，你可以把它们放在一起进行匹配。我认为这是其他贡献者提供的以下解决方案的精髓，但我认为您需要避免将所有字母拼凑在一起而没有空格。在英语中，您会以这种方式丢失信息。想一个以“th”音开头的短语。如果你把短语混在一起，你会失去哪个“th” 需要声音。“Theremin”（乐器）的“th”音与“There, a man”不同。

于 2012-03-28T01:53:30.707 回答
3

与Jonathan Barlow 的解决方案不同，我推荐一种 O(n 2 ) 算法，它可以为您提供您所寻求的属性，包括随机性、鲁棒性和可扩展难度。该算法的复杂性可以在恒定时间内或通过优化搜索方式进一步提高，但因为您的输入短语的大小保证很小，所以没什么大不了的。

  1. 构建牛津英语词典中所有已知单词的哈希表和按soundex()值列出的单词列表。这最初听起来很棘手，直到您意识到当前使用的实际上并没有那么多。假设一个体面的单向散列算法，这应该需要几兆字节。

  2. 将输入短语中的单词视为单个压缩字符串，没有任何单词标识，丢弃空格和所有标点符号。从这里开始，遍历所有字符长度的空间，从长度一开始，直到合并短语的全长减一。对于此遍历生成的每个字符串，针对 OED 执行哈希查找。当遇到字典中存在的单词时，将其单词和位置附加到内存列表的末尾。

    （这个过程总是需要sum(n)时间，这是根据定义0.5n(n+1)。所以，O(n 2 ) 它是。它的空间复杂度是最坏情况下的 O(n 2 )，但实际上，一组完全连接的术语是极不可能的。 )

  3. 现在是您的难度滑块。从生成的列表中，删除找到的前 N% 的术语，其中 N 是您的难度级别。这里的原则是，较小的词更容易让某人在词汇上处理，而较长的词更难发音和区分。

  4. 构造一个符合短语原始长度的数组（不包含空格和标点符号），并将遇到的单词列表打乱。现在，走洗牌列表。对于每个元素，验证数组中的所有槽是否在其原始位置都可用于该单词。如果是，请保留单词及其位置，将插槽标记为数组中使用的位置。如果不是，则迭代到下一个单词，直到列表用完为止。*

  5. 从最终的输出数组中，构造空间中未使用字符的分区列表，将每个字符包视为自己的短语。对于此列表，完全按照此处的草图执行音节检测，将结果传递metaphone()给以一定百分比的机会将两个或多个音节组合在一起。然后，对于来自 4. 的输出字典单词包，执行soundex()，从单词的可比较soundex值映射列表中拉出一个随机单词。soundex()根据列表的后备图，对于每个只能属于自己的单词，执行分区和metaphone()。最后，通过按位置排序将两个结果列表缝合在一起并打印结果。

这是一个随机算法，我认为它具有所有所需的属性，但在我看来它仍然很粗糙。

 * 额外积分：按字符或音节确定系统允许的重叠。这可以使接受的输出短语范围更大，难度更高。

于 2012-03-28T04:50:41.507 回答