java - 如何对 BinarySearch() 进行部分匹配

Question

我正在寻找一种使用二进制搜索进行部分匹配的方法。这是我的代码:

public void checkCardIndexForMatches(List<String> wordsToCheck) throws IOException {
    String[] cardIndexCache = cardIndexCreator.getCardIndexCache();

    for (String text: wordsToCheck){
        int i = Arrays.binarySearch(cardIndexCache, text.getText().toLowerCase().trim());

        if (i > 0){
            text.setCardIndexMatch(true);
        }
        //check if partial match
        //                  else if 
    }
}

到目前为止它的内容非常简单——基本上有一个外部文件被输入，文件中的每一行都作为一个数组存储在 cardIndexCache 中。当用户希望能够匹配数组中的“短语”(一个短语不止一个词，例如 Mohammed Ali)时，问题就来了。 wordsToCheck 参数中的单词仅作为单个单词传入。所以第一个词是 Mohammed 但二分查找失败了，因为它不知道第二个词是什么。我想不出一种简单的方法来让二进制搜索表明一个词有可能成为匹配项(第一部分匹配，只需附加下一个词并查看是否匹配)。

非常感谢任何想法!

Answer 1

这是我编写的一个 Trie 树以及一个基本上可以找到最大公共(public)前缀的搜索函数，相似性搜索是可能的，但成本很高..

---

class TNode
{
    public MapList<Char,TNode> next;

    public TNode ()
    {
        next = new MapList<Char,TNode>();
    }
}

---

class Trie
{
    TNode head;

    public Trie ()
    {
        head = new TNode();
    }

    public void insert (String t)
    {
        TNode cur = head;

        for (Char c : t.toCharArray())
        {
            if (!cur.next.containsKey(c))
            {
                cur.next.put(c,new TNode());
            }
            cur = cur.next.get(c);
        }
    }

    public boolean remove (String t)
    {
        Stack<Pair<Char,TNode>> path = new Stack<Pair<Char,TNode>>();
        TNode cur = head;
        Pair<Char,TNode> n = null;

        for (Char c : t.toCharArray())
        {
            if (!cur.next.containsKey(c))
            {
                return false;
            }
            path.push(c,cur);
            cur = cur.next.get(c);
        }

        while (path.size() > 0)
        {
            n = path.pop();
            if (n.getSecond().next.get(n.getFirst()).next.size() > 1)
            {
                break;
            }
            else
            {
                n.getSecond().next.remove(n.getFirst());
            }
        }
    }

    public boolean search (String t)
    {
        TNode cur = head;

        for (Char c : t.toCharArray())
        {
            if (!cur.next.containsKey(c))
            {
                return false;
            }
            cur = cur.next.get(c);
        }

        return true;
    }

    public String searchMaxPrefix (String t)
    {
        TNode cur = head;
        String match = "";

        for (Char c : t.toCharArray())
        {
            if (cur.next.containsKey(c))
            {
                match += c;
            }
            else
            {
                break;
            }
        }

        return match;
    }
}