php - 解谜: Finding All Words Within a Larger Word in PHP

Question

所以我有一个长度在 3 到 20 个字符之间的单词数据库。我想用 PHP 编写一些代码来查找较大单词中包含的所有较小单词。例如，“向内”一词中有“雨”、“赢”、“摆脱”等词。

起初我考虑在Words表中添加一个字段(Words3到Words20，表示单词中的字母数量)，例如“LetterCount”...例如，“rally”将表示为10000000000200000100000010:字母 A 的 1 个实例，字母 B 的 0 个实例，...字母 L 的 2 个实例，等等。然后，遍历每个表中的所有单词(如果指定了找到的单词的目标长度，则遍历一个表)并将每个单词的 LetterCount 与源单词的 LetterCount 进行比较(上例中的“向内”)。

但后来我开始认为这会给 MySQL 数据库以及 PHP 脚本带来太大的负载，调用每个单词的 LetterCount，将每个数字与源单词的数字进行比较，等等。

是否有更简单、或许更直观的方法来做到这一点？如果存储过程能以任何方式帮助减少开销，我愿意使用存储过程。只是一些建议将不胜感激。谢谢!

Answer 1

这是一个简单的解决方案，应该非常有效，但只能处理一定大小的单词(可能会分解大约 15-20 个字符，具体取决于组成单词的字母是否是低频字母)具有较低值或具有较高值的​​高频字母):

1. 根据每个字母出现的频率为每个字母分配一个素数。因此，使用 here 中的频率值，e 为 2、t = 3、a = 5 等。或一些类似的来源。
2. 通过乘以单词中字母的素值来预先计算单词列表中每个单词的值，并将其存储在表中的 bigint 数据类型列中。例如，tea 的值为 3*2*5=30。如果单词有重复的字母，则重复该因子，以便 teat 的值为 3*2*5*3=90。
3. 当检查一个单词(例如 rain)是否包含在另一个单词(例如 inward)内部时，只需检查 rain 的值是否足够 除向内 的值。在本例中，inward = 14213045、rain = 7315 和 14213045 可以被 7315 整除，因此单词rain 位于单词inward 内。
4. bigint 列的最大长度为 9223372036854775807，最多应包含 15-20 个字符(取决于单词中字母的出现频率)。例如，我从 here 中选取了第一个 20 个字母的单词。 ，它是 anitinstitutionalism，其值为 6901041299724096525，几乎无法放入 bigint 列中。然而，14 个字母的单词 xylopyrography 的值为 635285791503081662905，这个值太大了。您可能必须使用替代方法将非常大的情况作为特殊情况进行处理，但希望它们的数量足够少，这样仍然相对有效。

该查询的工作方式类似于我在这里准备的演示:http://www.sqlfiddle.com/#!2/9bd27/8