lucene

...有没具体实现过程的算法呢。哪儿有大哥大姐出来展示下最有效率的。

学习了.先研究研究.

个人想法：

建索引，然后排序，然后二分法查找索引，就能找到对应的URL

如果用KMP，那每次找个词都得遍历一次，ms不妥，如果建了索引，那就可以重复用了

想了一下，比较麻烦，kmp和二分是不可能解决这个问题，首先 忽略http://www, .net. .com等这些，只说中间内容部分,给url 加上一个辅助数字，int都行，使用前26位，每位代表a - z,1则有，0则无，辅助数字建1个索引，拿到模式串可迅速判断此行是否包含模式串所有该有的字母，如有再判断是否匹配，如果建26个索引，那就可直接找到有可能匹配行，忽略不可能的行，不过索引太多了

个人想法，未必可行：）

可以用多模匹配

kmp可以吧，其实一般情况下用正则就好了

倒排索引？

首先需要做的假设是需要这种模糊查询会被多次使用，比如动态查询，输入a，查询与a匹配的字符，然后输入b，查询如ab匹配的字符，如果只是一次查询，那遍历1亿条记录可能是较好的方法。

基于前面的假设，个人的思路是需要一种方法建索引：
1、按照字符（0-127）建所有字符的一个数组array，每个位置都代表一个字符，通过字符的ASCII码可以直接定位到字符。
   因此如果我们查询'a',那么包含'a'的URL都在这个数组值array[a]关联的对象中。
2、关键在于后续字符是如何处理，也就是存储在array[index]中的对象该如何建立数据结构。
   存储在array中的对象可以这样建立数据结构。
        + (index, pos)
   char |                index代表url的关联，pos代表char在url[index]的字符位置
        + (pos, index)
   × (index, pos)，可以按照index建立Hash，因为一个字符会在URL中出现多次，pos会有多个。
   × (pos, index)，可以按照pos建立Hash表或者开个大数组，数组大小为最长字符串的长度。  

因此在做实际查询的时候，按照先输入第一字符，比如'a'，到array[a]中查询步骤2所建立的结构，就可以知道含有a的url有哪些,建立index的set；然输入的是‘b’,这个时候我们需要查询array[b]就知道含有b的字符,这个时候就需要根据(index, pos)的每个pos，查询(pos+1, index)，然后在set中去掉没有b的index。后续的查询按照该步骤继续。

因为每个字符所出现的频率不一样，基本上在每个步骤过程中会排除的字符串个数不一，平均可能在60%-80%。效率应该可以接受。
不知道是否说明清楚自己的思路，可以查看附件的图像所建立的数据结构。

 
     

是1亿条数据。个人觉得用算法不好想的话，直接用lucene来实现。