使用soundex()或隐喻()创建Mad Gab风格短语的算法

Question

我正在尝试创建一个算法，该算法将建议使用Mad Gab风格的短语。

输入是一组短语。我也有一组关键字，我想在可能的时候使用。目前，我的解决方案只是暴力：

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

然而，我遇到的问题是：

• 考虑复合关键字，例如"catches"可以是"catings"、"cat"+"cheese"
• 允许使用文字术语——"the"、"and"、"one"、"two"、"three"
• 如何建议非关键字的术语。即当找不到关键字或文字时，返回到类似于系统字典的东西上
• 跳过短语段。现在它只通过一次。但考虑一下这样的情况：短语以不匹配的内容开头，但几个字符之后包含匹配的内容

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

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

Answer 1

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

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

如果你想要一种更技术、更准确的方法，有一篇关于如何做到这一点的博士论文：

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

然后使用你自己滚动的东西或隐喻（）将每个音节变成语音表示。你可以使用类似的网站来解释元音规则。这些只是概括。如果你自己滚动，你将分别处理元音和辅音。元音素只使用辅音，这很好，但不像你也考虑元音那样酷。

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

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

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

示例：

"逻辑后果"

A。音节split

"lo gi cal con sequence"

B。应用的元音

"lah gee cahl con see quince"

C。应用的辅音

D。声音文本测试（单音节声音文本-显然太容易猜测，但它证明了这个概念）

"Law Gee Call Con Sea Quints"

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

Soundex MySQL比较的一个例子是：

选择strcmp（soundex（'lah'），soundex）；

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

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

更新：

我并不是想暗示我的解决方案只会产生一个音节的单词。我用了一个音节作为例子，但如果你把其中两个音节放在一起，你会得到多音节的匹配。事实上，您可能只是从将所有音节干扰在一起并在mysql中运行soundex开始。如果你能找到答案，那就太好了。但是，你可以去掉音节，直到你能得到最长的匹配。然后你就剩下短语的结尾了，可以把它们放在一起进行比赛。我认为这是另一位投稿人提出的解决方案的精髓，但我认为你需要避免将所有字母无空格地挤在一起。在英语中，那样你就会丢失信息。想象一个以"th"开头的短语。如果你把短语塞在一起，你就失去了需要哪个"th"音。"Theremin"（乐器）的"th"音与"There，a man"不同。

Answer 2

采用与Jonathan Barlow的解决方案不同的策略，我推荐一种O（n²）算法，该算法在随机性、鲁棒性和可扩展性方面为您提供所需的属性。该算法的复杂性可以在恒定时间内或通过优化搜索模式来进一步提高，但由于输入短语的大小保证很小，所以没什么大不了的。

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

2. 将输入短语中的单词视为一个单一的压缩字符串，没有任何单词标识，丢弃空白和所有标点符号。从这里开始，遍历所有字符长度的空格，从一开始，一直到合并短语的全长减去一。对于这次遍历生成的每个字符串，根据OED执行哈希查找。当遇到字典中存在的单词时，将其单词和位置附加到内存中列表的末尾
   
   （此过程将始终花费sum(n)时间，根据定义为0.5n(n+1)。因此，它是O（n²）。它的空间复杂性是最坏情况下的O（n^{2），但在实践中，完全连通的项集是极不可能的。）}

3. 现在是你的难度滑块。从生成的列表中，去掉找到的术语的前N%，其中N是你的难度等级。这里的原则是，较小的单词对某人来说更容易进行词汇处理，而较长的单词则更难发音和区分。

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

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

这是一个随机算法，我相信它具有所有想要的属性，但在我看来仍然很粗糙。

---

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