范围搜索3列的字符串

我已经设置字符串像下面 A.B.C范围搜索3列的字符串

a1.b1.c1 
a1.b1.c2 
a1.b2.c3 
a2.b1.c1 
a2.b2.c2 
a3.b3.c3

如果要求a1.*它应该返回我从a1开始，所有的字符串。如果要求a1.b1，那么应该返回所有的字符串从a1.b1

开始所有的输出应在排序方式（字典）

任何建议在数据结构，我想的是Suffix Tree。

来源

2013-03-21 Avinash

一个简单的列表和一些正则表达式模式匹配来过滤元素呢？ – 2013-03-21 04:38:08

此代码可能会对您有所帮助。

String stringarray[] = {"a1.b1.c1", 
"a1.b1.c2", 
"a1.b2.c3", 
"a2.b1.c1", 
"a2.b2.c2", 
"a3.b3.c3"}; 
String startingfrom = "a1.b1"; 
for(int i = 0; i < stringarray.length;i++) { 
    if(stringarray[i].startsWith(startingfrom)) 
       System.out.println("string is : " + stringarray[i]); 
}

来源

2013-03-21 04:42:53 Dhinakar

如果你的字符串集基本上是固定的（不经常更新），那么简单的排序列表就可以。要查找带有前缀的所有字符串，请在该列表上执行二进制搜索，找到第一个字符串。然后在字符串匹配前缀的同时迭代。

就内建的Java数据结构而言，我建议使用TreeSet。

SortedSet<String> data = new TreeSet<String>(); 

Set<String> findMatching(SortedSet<String> data, String prefix) { 
    String prefix = prefix.replace("*", ""); // remove unnecessary * 
    String nextPrefix = prefix + '\uffff'; // a string guaranteed to be after anything matching the prefix 
    // get the subset after the prefix, and then get the subset of that before the prefix 
    return data.tailSet(prefix).headSet(nextPrefix, false); 
} 

findMatching(data, "a1.b1.*");

使用nextPrefix是有点难看，因为我已经假定前缀永远是. - 分隔部分序列，并追加FFFF字符得到一个字符串大于任何匹配前缀的最佳方式。做这部分可能有更好的方法。

来源

2013-03-21 04:46:11 Edmund

NavigabeeSet可以做这样的事情，快速：

NavigableSet<String> s = new TreeSet<>(); 
    s.addAll(Arrays.asList("a1.b1.c1", "a1.b1.c2", "a1.b2.c3", "a2.b1.c1")); 
    System.out.println(s.subSet("a1.", true, "a2", false)); // a1.* 
    System.out.println(s.tailSet("a1.b1"));     // a1.b1

输出

[a1.b1.c1, a1.b1.c2, a1.b2.c3] 
[a1.b1.c1, a1.b1.c2, a1.b2.c3, a2.b1.c1]

来源

2013-03-21 05:04:06

我的功能：

class Match 
{ 
    public static ArrayList<String> match (String[] data, String regex) 
    { 
     ArrayList<String> m = new ArrayList<String>(); 

     for (String d : data) 
     { 
      if (d.matches(regex)) 
      { 
       m.add(d); 
      } 
     } 

     Collections.sort(m); 

     return m; 
    } 
}

测试：

String data [] = 
{"a1.b1.c1", 
"a1.b1.c2", 
"a1.b2.c3", 
"a2.b1.c1", 
"a2.b2.c2", 
"a3.b3.c3"}; 

// match using a regular expression 
ArrayList<String> matched = match (data, "^a1\.b1.*");

来源

2013-03-21 06:27:53

您可以创建一个3d树（kd-tree的特例）。然后在a1.b1.*之类的东西上进行搜索，您可以在a1.b1.c1_min和a1.b1.c1_max上进行范围搜索。并对输出进行排序。

这将使你O (n^(2/3) + r)搜索和O (r log (r))的排序，其中n是所有节点的数量和r是发现节点的数量。

搜索复杂度如下从一般kd-tree的搜索复杂度来看：O(n^(1-1/k) + r)，在3d树的情况下，k是3. ^是为了权力。

来源

2013-03-21 08:02:54

范围搜索3列的字符串

回答

相关问题