请教个算法 -- 给英文书制作索引

Question

要给一本英文电子书做个索引，就是所有关键字的索引但是，不告知什么是关键字也就是说，书中所有的字都要遍历一遍，不得有遗漏然后所谓索引，即是所有关键字所出现的所有页数，比如EntityManager 78,113, 687请问如何设计算法？如果允许多线程操作如何优化配置多线程实现这个任务？谢谢

Answer 1

不知道什么是关键字就是最大的问题！你首先需要有个词库，因为并不是一个单独的单词就可以作为关键字的；反之：关键字也不是全都仅一个单词。否则你整理出来频度最高的，基本上就是：the、and、so、is、in 之类的东西，稍好点就是：java、program、class、package、public，这些东西能有用么？对于图书检索系统而言，首先需要有个词库，而且这个词库还必须分学科门类的，不能是通用的。只有词库内的单词，在最终统计时才会纳入范畴。
至于多线程，这个比较简单，就没啥好说的了，自己看看 Map/Reduce 就是了，一个思路。

Answer 2

谢谢回答其实是个过往的面试题，昨天突然想起来，发帖问问，因为下周又要有面试但是，似乎挺不错的一道题确实没有关键字库当时的考官说是一个假象的环境其实是要考察对一本英文书中所有单词找出所有存在页数的最简方法允许多线程也就是说，关键字要在最后出了结果后在考虑
我能想到的就是多个线程去访问多个页面，每个线程将<单词，页数>对放入hashmap然后将所有生成的hashmap合到一起。但这个解决问题的方法的问题是每一页的页数在当页的线程内的hashmap都是一样的所以似乎很浪费资源请给想想办法。谢谢了

Answer 3

浪费资源不是问题，要么时间换空间，要么空间换时间。该舍弃啥就舍弃啥，有舍才有得。问题是所浪费的资源是否合理而已。你关于按照页面去拆分任务并执行的大思路没问题，细节问题只是在任务分配的模式与合并结果集的时机而已。比如：
◎ 主线程维护一个总HashMap，负责记录每个关键字所有页码情况；
◎ 主线程启动10个子线程；
◎ 10个子线程自行维护自己的一个HashMap；
◎ 10个子线程找主线程要任务（页码）；
◎ 每个子线程处理完毕后，将结果交给主线程合并，然后清空HashMap，继续要下一个任务（页码）。
这种情况下，总共也就 11 个HashMap，为啥会觉得很浪费资源？

Answer 4

哦，把自己也绕糊涂了，子线程不需要HashMap，用Collection<String> 就行了。

Answer 5

谢谢那就是还需要有一个关键字列表了？如果没有关键字，全书都要扫描和记录，也可以这么做么，不会搞得主线程里的HashMap超大吗？

Answer 6

另外请您给详细说说，主线程的主HashMap里面是什么个格式？是不是<单词，ArrayList<String>页数>？还是 <页数, ArrayList<String>所有此页单词>？
谢谢

Answer 7

这个是根据检索需要来定，一般多半是前者，因为多半是找关键词所在位置。不过我记得ArrayList应该不支持直接扩容吧？建议用支持自动扩容的来存储页码，比如：
HashMap<String keyword, Collection<Integer> pagenums>