大量字符串比较的问题，急需高效方法，多谢

Question

问题是这样的：
由两组字符串集合A和B：A很大，设为1w个不同的单词，按字母顺序从小到大有序排列；
                      B比较小，设为300个不同单词，无序
                      A包含B的绝大部分词，只有很少部分不包括。
要求是找到B的每个词（如果A包含这个词）在A中的位置。 1. 我现在的办法是先搜索一遍B, 排除掉A（有别的途径知道，不需要读一遍A）没有的字然后生成一个新的数组C，循环300次。2. 然后sort C，让他也从小到大排列。复杂度未知，java自带的。
 
3. 然后从A的末尾开始搜索C的最后一个，找到之后再从停下的位置开始搜C的倒数第2个。因为A肯定包含C，他们又都有序排列，所以n肯定在n-1之前被搜到。循环10000次程序要进行很多次这个比较的，大概平均500次，所以运行起来是很慢的，这还仅仅是预处理的部分，这么满是无法接受的有什么高效率的办法吗？非常感谢

Answer 1

你可以先对B中的先快速排序
然后从B中的最小（或最大）可是在A中搜索，使用二分查找法，这样可以提高效率。而在搜索下一个单词的时候，只需要从上一个已经搜索的位置继续即可。

Answer 2

lz可以使用多线程查找(4个线程)
1.将B排序
2.从A中的len/2位置往后找,找到B中的位置,这个时候A和B都被分成两段(最差的情况是B的两段一个为0,一个还是B)
3.对A的两段还用同样的方法再分一次,这时A被分成4段,B也一样(最差情况是B三个为空,一个还是B)
4.这时只需要对对应的A B字段搜索就可以了.

Answer 3

jigangwang(wang) ( )  的多线程方式不可取
需要同步，不如单线程。
如果真的要多线程只能在查找这个过程使用

Answer 4

二分法查找
http://blog.csdn.net/douzixinxin/archive/2006/02/21/604144.aspx

Answer 5

1、先将 B 按照 A 的顺序排列。然后定义两个“指针”indexA = 0; indexB = 0;
2、将 indexA 往后移动，每移动一次就比较两“指针”所在位置的字符串；
3、相等的话就记录两个“指针”的位置，indexB往后移动一次，跳到步骤2；
4、如果不相等的话， indexA 继续移动；
5、重复3或4。如果 indexA 到末尾了就表示 A 中不存在 B 的当前元素。这时候将 indexA 置为上次记录的位置（这就不需要从头比较起了）。
6、这样一直到 indexB 移到末尾。至此，indexB 仅仅循环一次，indexA 可能循环若干次，但每次循环的量会越来越少，循环的次数就要看 B 中有多少单词不在 A 中了。这样做的效率应该挺高的。

Answer 6

如果我上面没有说清，下面是我写的一个例子：/**
 * QuickCompare.java
 * 创建时间：2006-7-27
 * 创建人：HYD
 */
package csdn.quickcompare;import java.util.Arrays;/**
 * @author HYD
 */
public class QuickCompare {    /**
     * 比较字符串数组
     * 
     * @param a
     *            字符串数组
     * @param b
     *            字符串数组
     */
    public static void quickCompare(String[] a, String[] b) {
        if (a == null || b == null) {
            return;
        }
        Arrays.sort(a); // 如果已经排好了序，这步就可以去掉了
        Arrays.sort(b); // 如果已经排好了序，这步就可以去掉了        int indexA = 0, indexB = 0;
        int lastPosA = indexA;
        int counter = 0;        while (indexB < b.length) {
            counter++;
            System.out.println("比较 " + a[indexA] + " 和 " + b[indexB]);
            if (a[indexA].equals(b[indexB])) {
                System.out.println("在 A 中找到 " + b[indexB] + ", 位置：" + indexA);
                lastPosA = indexA;
                indexB++;
                indexA++;
            } else {
                indexA++;
                if (indexA > a.length - 1) { // 已经到了数组 A 的末尾
                    System.out.println("在 A 中没有找到 " + b[indexB]);
                    indexA = lastPosA + 1;
                    indexB++;
                }
            }
        }        System.out.println("查找完成，一共比较了 " + counter + " 次。");
    }    /**
     * @param args
     */
    public static void main(String[] args) {
        String[] a = {"ah", "bad", "cow", "dish", "frog", "google", "line", "mm", "what", "xman", "yes", "zoo"};
        String[] b = {"ah", "frog", "little", "mm", "zoo"};
        
        quickCompare(a, b);
    }}

Answer 7

hi，谢谢，YidingHe(机枪兵) 
我是从最前面最后面同时搜，搜索到之后就去掉前面和后面的部分，这样每次搜索的区间会不断减小，不过不比最开始的办法快多少，几乎是一样，我也无法理解期间并没有做别的工作，也没有io访问之类的，太奇怪了，或许String的比较本身比较慢。boyu_song，你说得很对，我没想到，尝试一下，多谢

Answer 8

首先将A中的做HASH排序，以字母作为索引，
每个索引冲突上的值按大小顺序做链式排序，
这样1W个被分成26个列，每个列平均400如果你觉得不好的话，还可以对每个链的第2字母再做一次以上操作

Answer 9

hi, f_acme(沧海一声笑) 
我也觉得用二分法效率应该挺高了，可是处理完一个文件的搜索大概需要1秒半多点，搜索引擎每次至少返回几百上千个文件，不可能指望用户等这么久。而且这只是最基本的特征空间，我说的也是最简单的情况，实际要处理的多得多，字典大概有三百多万个符号，不知道筛选完会剩下多少。hi，xuyang821225(CSDN账号) 
谢谢，很有道理，尝试一下我是不明白为什么用了binary search跟不用速度差不多呢