问题如下: 对一个字符串数组进行过滤.
字符串数组可能很大,一个例子是:{"北京","北京朝阳","北京朝阳饭店"}.
给定的字符串是按字数排好序的.
要求是经过算法过滤后得到结果:{"北京","朝阳","饭店"}
也就是拿前面的字符串去过滤后面的字符串,得到一个最简字符串数组.
我自己的算法解决1万词的时间约1秒. 我希望再快一些.
求算法高手解决.
仅仅是尽快滤出之前没有的词，
import java.util.Comparator;
import java.util.TreeSet;
public class Test {
static public int removeOccurances(StringBuilder buf,String word){
int c=0,p,len=word.length();
for(;(p=buf.indexOf(word))!=-1; c++)
buf.delete(p, p+len);
return c;
}
static public void main(String argv[]){
String a[]={"北京","中国朝阳","北京朝阳","天津包子","中国北京",
"北京烤鸭","中国中国","北京中国饭店","北京北京北京",
"北京朝阳饭店","北京朝阳烤鸭饭店","中国北京朝阳饭店"
};
TreeSet<String> set=new TreeSet<String>(new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
int r=o1.length()-o2.length();
return r==0? o1.compareTo(o2):r;
}
});
StringBuilder buf=new StringBuilder();
for(String w:a){
buf.setLength(0); buf.append(w);
for(String dw:set) removeOccurances(buf, dw);
if(buf.length()>0){
w=buf.toString();
for(String dw:set)
if(buf.length()<dw.length()){
buf.setLength(0); buf.append(dw);
if(removeOccurances(buf, w)>0){
set.remove(dw); set.add(buf.toString());
}
}
set.add(w);
}
}
System.out.print(set);
}
}
===========
[中国, 北京, 朝阳, 烤鸭, 饭店, 天津包子]
效率应该是O(2W*D), W为数组长度，D为有效词数量
把你的算法拿来看看。应该多说自己追问
我的代码不好贴.我都是写成一个一个函数然后互相调用的.
我贴下主调函数吧. 其中有个函数gsubAll,是把x[]粘贴成一个长字符串,然后把temp全部从中删除.
你的算法效果比较好,速度稍慢.
public static String[] clearRoots_old(String x[])
{
String temp=new String ();
for(int i=0;i=2)
{
temp=x[i];
x=gsubAll(temp,x);
x[i]=temp;
}
}
return x;
}
连成长串，等于拿内存换时间...
其实吧，我觉得这个命题需求有点不明确.所以很束手
理由:
如果你的词是有语义的，即不能出现“的得”“京烤”这样无意义的中文。就涉及中文分词，一个更复杂更系统的课题。
如果你的词是无语义（允许出现“的得”“京烤”）。本来可以按压缩算法处理去掉所有的重复字符。编码的单位是字符，但你又可能潜在要求要从2个字以上的“词”开始，不完全压缩，计算效率也上不去..
需要定义一下滤出的"词"是什么？
滤除的词应该是那些经常重复出现的词.但是你说的"京烤"这种词可能也会出现的.因为他们俩的条件概率比较大.如果能够做到进一步处理非词的词就更好了.我想目前先做简单的,就是把一个字符串数组中的反复出现的词提取出来.
追答允许“京烤"，那按无语义处理， 那如果重复出现最多的是“京”1个字呢？
还是要定义什么是“词”。汉语意义上的"词组"是有语义的。所以我不能按词组来理解你的需求。
定义什么是“你要的词”比如长度要求、重复次数、文字系统("京","京A"，"12","AB","hello" 日本字，阿拉伯字,，算不算词？)，等其他细节要求。
我看你还没想过什么什么是词，所以这么写下去也没有结果的。
另外，分词问题不是这里"许个愿""头脑风暴"就能简单解决的吧，中科院都有相应的前沿项目。鼓励研究但也要全面认识..
谢谢. 你回答挺好. 下面在交流吧. 留个联系方式哦.
算法时间复杂度为线性阶，即O(n)，应该能够满足你的要求。
对数阶的时间复杂度O(log n)，目前还想不出来，呵。
Java程序：
public class Test16 {
public static void main(String[] args) {
String[] arr = arr = new String[]{"北京","北京朝阳","北京朝阳饭店","北京朝阳饭店住宿部","北京朝阳饭店住宿部五楼","北京朝阳饭店住宿部五楼三二一一房"};
filtrateArray(arr);
for(String str : arr){
System.out.println(str);
}
}
public static void filtrateArray(String[] arr){
for(int i=arr.length-1; i>0; i--){
arr[i] = arr[i].substring(arr[i-1].length());
}
}
}
运行测试：
北京
朝阳
饭店
住宿部
五楼
三二一一房
我估计你的算法是这样的：
for(int i=1; i<arr.length; i++){
for(int j=i; j<arr.length; j++){
arr[j] = arr[j].substring(arr[j-1].length);
}
}
这是一个平方阶O(n*n)，如果字符串是10000长度的话，计算次数近5000万次，相当惊人。追问
我的算法不是平方时间. 虽然有2个循环,第二个循环是把所有词先连接起来,然后把arr[i]过滤.而且你的算法和我的要求有点不一样. 你的算法只能处理前缀词?
现在大多分词系统有个通病,就是对未登录词的识别较弱.我想做一个程序从大量重复词提取未登录词.比如"凡客女装". 分词系统一般分不出"凡客". 但是用我自己的程序可以提取到"凡客".
