如何做BinarySearch的部分匹配（）

我正在尋找一種使用二分搜索進行部分匹配的方法。這裏是我的代碼：如何做BinarySearch的部分匹配（）

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參數中的單詞僅作爲單個單詞傳入。所以第一個詞將是穆罕默德，但二分查找失敗，因爲它不知道第二個詞是什麼。我不能想到一個簡單的方法來獲得二進制搜索，以表明一個詞有潛力成爲一個匹配（第一部分匹配，只是追加下一個單詞，看看是否匹配）。

任何想法非常感謝！

來源

2012-09-27 maloney

您是否知道如果找不到項目，binarySearch不會返回-1？它返回 - *（如果它存在，項目的索引）*。如果你不想實際實現一個二進制搜索或者一個trie，你可以使用該返回值來僞造它。 –

感謝您的提示！我會給出一個去看看我如何... – maloney

二進制搜索用於確切的情況下搜索..按字母順序排列的字符串進行二進制搜索由數字索引指導，是一個最終的確切情況下的搜索..做一個好的搜索算法，你建立一個trie，並做一個最大共同前綴作爲近似或找到另一種方法，這將是更困難的 –

這裏有一個特里，我與主要發現的最大公共前綴搜索功能一起寫的，一個相似性搜索是可能的，但將是昂貴的..

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; 
    } 
}

來源

2013-06-18 05:26:53

如何做BinarySearch的部分匹配（）

回答

相關問題