所以我有一个长度在 3 到 20 个字符之间的单词数据库。我想用PHP编写一些代码,以查找包含在较大单词中的所有较小单词。例如,在"向内"一词中有"雨","赢","骑"等词。
起初我想到在单词表中添加一个字段(单词3到单词20,表示单词中的字母数),类似于"字母计数"......例如,"拉力赛"将表示为 10000000000200000100000010:字母 A 的 1 个实例,字母 B 的 0 个实例,...字母 L 等的 2 个实例。然后,遍历每个表中的所有单词(如果指定了找到的单词的目标长度,则检查一个表),并将每个单词的 LetterCount 与源单词的 LetterCount 进行比较(在上面的示例中为"向内")。
但后来我开始认为这会给MySQL数据库和PHP脚本带来太多的负载,调用每个单词的LetterCount,将每个数字与源单词的数字进行比较,等等。
有没有更简单,也许更直观的方法来做到这一点?我愿意使用存储过程,如果它以任何方式有助于减少开销。只是一些建议将不胜感激。谢谢!
这是一个简单的解决方案,应该非常有效,但只能达到一定大小的单词(可能大约 15-20 个字符会分解,具体取决于构成单词的字母是具有较低值的低频字母还是具有较高值的高频字母):
- 根据每个字母的频率为其分配一个质数。 所以
e
是 2,t
= 3,a
= 5,等等,使用这里或类似来源的频率值。 - 通过将单词中字母的素数值相乘来预先计算单词列表中每个单词的值,并将其存储在表中的
bigint
数据类型列中。 例如,tea
的值为3*2*5=30
。 如果单词有重复的字母,请重复该因子,以便teat
的值应为3*2*5*3=90
。 - 当检查一个单词(例如
rain
)是否包含在另一个单词(例如inward
)中时,检查rain
的值是否除以inward
的值就足够了。 在这种情况下,inward = 14213045
、rain = 7315
和14213045
可以被7315
整除,所以单词rain
在单词inward
内。 - 一个 bigint 列的最大值为
9223372036854775807
,最多 15-20 个字符应该没问题(取决于单词中字母的频率)。 例如,我从这里拿起了第一个 20 个字母的单词,它是anitinstitutionalism
的,并且其值为6901041299724096525
,几乎无法放入 bigint 列。 但是,14个字母的单词xylopyrography
的值为635285791503081662905
,这太大了。 您可能必须使用替代方法将真正大的问题作为特殊情况处理,但希望它们的数量足够少,以至于它仍然相对有效。
该查询的工作方式类似于我在这里准备的演示:http://www.sqlfiddle.com/#!2/9bd27/8