作者ken915007 (Ken_Wu)
看板java
標題[問題] 字串比對的效率
時間Fri Dec 4 22:56:14 2009
目前正在使用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
1F：→ tkcn:input 都會是數字嗎? 12/04 23:03
2F：→ tkcn:input 那裡我有看沒有懂 12/04 23:04
3F：→ ken915007:我只是用數字測試~會是中文詞...或英文單字~等等的 12/04 23:06
4F：→ ken915007:我是想用text mining上，會是non-structural資料... 12/04 23:09
5F：推 snowlike:所以該例要得到2？感覺上是n-gram，可以搜尋相關演算法 12/04 23:22
我剛剛去search了n-gram方法…不是這個…
我主要的是玩關聯規則…像aprior等等的，裡面就會有data跟n-itemset的比較
但我主要不是在方法的部分…因為方法我有找到相關方法的code針對structural資料
也看過code了，但我要把方法改成對non-structural的資料
※ 編輯: ken915007 來自: 140.130.36.90 (12/04 23:40)
6F：推 slalala:好酷 Map<String,Set<String>> 12/05 02:01
7F：推 qrtt1:看能不能在資料前處理時統一成數字, 要結果再轉成字串 12/05 08:20
8F：→ ken915007:若item要是多的話…這樣轉數字~最後在反轉~也是要時間 12/05 12:12
9F：→ ken915007:酷!! 難道不能這樣用?還是比較不好?? 12/05 12:14
10F：→ qrtt1:處理簡單的型別絕對比物件來的有效率 12/05 13:41
11F：→ qrtt1:關聯用 fp-tree 比較有效率的說 :P 12/05 13:43
嗯! 我有看過這些方法~但精準度apriori會比較高點...所以才想用apriori，
但缺點就是要重覆掃資料...
有點離題了^^ 重點不是這演算法= =
我想知道對於字串的比對~像上面的範例~大家會用什麼方法去比對是否有出現過
※ 編輯: ken915007 來自: 140.130.36.90 (12/05 14:33)
12F：推 KanoLoa:先排序再說 ? 12/05 15:33
13F：→ ken915007:先排序在說???~那我不用HashSet改用SortedSet? 12/05 17:04
14F：推 MephistoH:阿咧...不是都用正則表示嗎 = = ?? 12/05 19:44
15F：→ ken915007:正則表示!!能用於中文類型? 我還試過 12/05 20:10
16F：→ jej:一個很笨的方法..如果都是String的話..可以試看看轉成byte[] 12/05 23:38
17F：→ jej:然後用apache common作byte[]比較..唯一的就放到array裡面 12/05 23:40