拼图解决:在PHP中查找较大单词中的所有单词

Question

所以我有一个3到20个字符长的单词数据库.我想用PHP编写代码,找到包含在一个更大的单词中的所有较小的单词.例如,在"向内"一词中有"rain","win","rid"等字样.

起初我想到在Words表中添加一个字段(Words3到Words20,表示单词中的字母数),类似于"LetterCount"......例如,"larally"将表示为10000000000200000100000010:1个实例字母A,字母B的0个实例,......字母L的2个实例等.然后,遍历每个表中的所有单词(如果指定了找到的单词的目标长度,则查看一个表)并比较每个单词的LetterCount到源字的LetterCount(上例中的"向内").

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

有没有更容易,也许更直观的方式来做到这一点？我愿意使用存储过程,如果它能以任何方式帮助增加开销.只是一些建议将不胜感激.谢谢!

Answer 1

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

1. 根据频率为每个字母分配一个素数.所以e是2,t= 3,a= 5等,使用来自这里或某些类似来源的频率值.
2. 通过将单词中字母的素数值相乘,预先计算单词列表中每个单词的值,并将其存储在bigint数据类型列中的表中.例如,tea将具有值3*2*5=30.如果一个单词有重复的字母,请重复该因子,以使其teat值为3*2*5*3=90.
3. 当如果一个词检查,例如rain,包含在另一个词里面,比如inward,它是足够的检查,如果该值rain除以该值inward.在这种情况下,inward = 14213045,rain = 7315,和14213045是整除7315,所以这个词rain是词里面inward.
4. bigint列9223372036854775807最大,最多约15-20个字符(取决于单词中字母的频率).例如,我从这里拾取了第一个20个字母的单词,这个单词anitinstitutionalism的值6901041299724096525很大,几乎不适合bigint列.但是,14个字母的单词xylopyrography的值635285791503081662905太大了.您可能必须使用备用方法处理非常大的特殊情况,但希望它们足够少,它仍然相对有效.

该查询将像我在这里准备的演示一样:http://www.sqlfiddle.com/#!2/9bd27/8