[問題] 字串比對的效率

[ken915007 (Ken_Wu)]

目前正在使用java實作data mining的方法...
實作中，在想一個問題，就是字串比對
怎樣的字串比對才有效率?

例如：
input的字串：2 5 7 8 10 15 19
比對字串的陣列：{2 10, 5 8 19, 3 7 10 13}
還有一個map在記錄count

動作是input的字串會分別跟這三個比對，
看是不是在input中有出現，
有出現的話就在map中+1動作

input的資料筆數少那是還好，
但資料筆數多，或比對字串的陣列一多
不知大家會怎樣做比對...

目前是看了一些，有用split分割資料放在String[]中，
或用StringTokenizer方法切割資料，最後跑雙迴圈或三迴圈比對，
後來就在找一些包含或比對的東西，
發現在Set中的containsAll方法可以做Set比對，其code如下：

import java.util.*;

public class Test3 {
    public static void main(String args[]){
//      比對的內容
        String[] sArray = {"2 10", "5 8 19", "3 7 10 13"};
//      宣告要比對的Map及計數器的Map
        Map<String,Set<String>> checkMap = new HashMap<String,Set<String>>();
        Map<String,Integer> countMap = new HashMap<String,Integer>();
//      先把比對的陣列轉成map，
        for(String str: sArray){
             Set<String> checkSet = new HashSet<String>();
             checkSet.addAll(Arrays.asList(str.split(" ")));
             checkMap.put(str, checkSet);
             countMap.put(str, 0);
        }

//      要比對的資料
        String input = "2 5 7 8 10 15 19";
//      把資料轉成Set
        Set<String> inputSet = new HashSet<String>();
        inputSet.addAll(Arrays.asList(input.split(" ")));

//      資料比對
        for(String key:checkMap.keySet()){
             if(inputSet.containsAll(checkMap.get(key)))
                 countMap.put(key, countMap.get(key)+1);
        }

//      印出countMap筆數
        for(String key: countMap.keySet())
            System.out.println("item=" + key + ", Count=" + countMap.get(key));
    }
}

output的結果如下：
item=2 10, Count=1
item=5 8 19, Count=1
item=3 7 10 13, Count=0

input的資料可能透過讀檔的方式
那筆數可能萬、十萬、百萬、千萬…都有可能

所以，我只想討論一下~大家覺得怎樣比對較有效率^^
還是有其他比較好的建議…

感謝各位!!

Best regards,


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.130.36.90
→ tkcn:input 都會是數字嗎?
→ tkcn:input 那裡我有看沒有懂
→ ken915007:我只是用數字測試~會是中文詞...或英文單字~等等的
→ ken915007:我是想用text mining上，會是non-structural資料...
推 snowlike:所以該例要得到2？感覺上是n-gram，可以搜尋相關演算法
我剛剛去search了n-gram方法…不是這個…
我主要的是玩關聯規則…像aprior等等的，裡面就會有data跟n-itemset的比較
但我主要不是在方法的部分…因為方法我有找到相關方法的code針對structural資料
也看過code了，但我要把方法改成對non-structural的資料
※ 編輯: ken915007       來自: 140.130.36.90        (12/04 23:40)
推 slalala:好酷  Map<String,Set<String>>
推 qrtt1:看能不能在資料前處理時統一成數字, 要結果再轉成字串
→ ken915007:若item要是多的話…這樣轉數字~最後在反轉~也是要時間
→ ken915007:酷!! 難道不能這樣用?還是比較不好??
→ qrtt1:處理簡單的型別絕對比物件來的有效率
→ qrtt1:關聯用 fp-tree 比較有效率的說 :P
嗯! 我有看過這些方法~但精準度apriori會比較高點...所以才想用apriori，
但缺點就是要重覆掃資料...
有點離題了^^ 重點不是這演算法= =
我想知道對於字串的比對~像上面的範例~大家會用什麼方法去比對是否有出現過
※ 編輯: ken915007       來自: 140.130.36.90        (12/05 14:33)
推 KanoLoa:先排序再說 ?
→ ken915007:先排序在說???~那我不用HashSet改用SortedSet?
推 MephistoH:阿咧...不是都用正則表示嗎 = = ??
→ ken915007:正則表示!!能用於中文類型? 我還試過
→ jej:一個很笨的方法..如果都是String的話..可以試看看轉成byte[]
→ jej:然後用apache common作byte[]比較..唯一的就放到array裡面