我有一个巨大的列表,大约有 100 000 行,如下所示:
- ipad新闻
- 阿基帕德
- cddeffipad
- 地狱世界
- iworldthis .. 等等
并且想找到流行的子字符串,在这种情况下,“ipad”将是最受欢迎的,“world”将排在第二位。最小长度应为三个或四个字符。
我无法预测子字符串,所以使用字典是不行的。
我有一个巨大的列表,大约有 100 000 行,如下所示:
并且想找到流行的子字符串,在这种情况下,“ipad”将是最受欢迎的,“world”将排在第二位。最小长度应为三个或四个字符。
我无法预测子字符串,所以使用字典是不行的。
我将使用以下逻辑流程来解决这个问题:
提取每个单词的后缀集。所以从“ipadnews”我们得到:“ipadnews”、“padnews”、“adnews”等等。这样,“新闻”将是后缀之一,而不是“ipad”。
为了弥补上述步骤中缺少的子字符串,还要提取前缀。我们得到“ipadnew”、“ipadne”等,包括“ipad”。
对于上面的每个子字符串,将它们散列到一个计数中,例如 $hash{$substr}++。
最后,我们将有一个长哈希表,其中单词的频率作为值。假设您只想要 10 个最流行的单词,而不是昂贵的排序。从一开始就保留一个集合,其标准是其中的任何单词的分数都必须高于当前的最低分数。您可以使用最低分数跟踪单词,当您添加分数高于最低分数的第 11 个项目时,将最低分数的单词剔除并更新最低分数指针。
哈希表中的最大键数为 2*k*n,其中 k 是单词的平均长度,n 是单词的总数。