作者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