在Java中搜索二维字符串数组的字符串。

4
我有一个二维字符串数组,看起来像这样: enter image description here
第一列包含许多字符串的字符,其他列是字符的额外数据。
我想在这个数组中搜索一个字符串(可能要转换为字符数组),以获取所有匹配的索引(起始-结束)。例如,当我使用关键字“next”进行搜索时,结果应该是[5 - 8],[13 - 16](如上图所示的高亮部分)。
简而言之,我需要一个类似于这样的方法:
  public static List<Interval> search(String searchText, String[][] data, int columnsCount, int rowCount){
      // Convert search text to String array
      String[] searchArr = getStringArray(searchText);
      // then search in data

  }
  
  // where Interval is:
  public class Interval{
       public int start;
       public int end;
  }   

有没有快速的搜索方式,因为我的数据非常大?
提前致谢!


最有效的搜索之一是“二分查找”。可以实现“红黑树”或“AVL树”以进行更有效的搜索。 - erencan
2
有很多字符串搜索算法 - Domi
1
另外,请注意,如果您的数组包含[字母1,数据,数据,数据...,字母2,数据...],则会得到较差的缓存命中率,这对于处理大型数据集时的性能至关重要。尝试重新排列数据,如[字母1,字母2,...字母N,数据,数据,...]。这就是为什么。(不要介意他谈论C++,这适用于所有语言)。 - Domi
4个回答

3
我建议将String[][]调整为CharSequence。这样,您就可以自由地使用CharSequence进行操作,这也意味着您可以使用java.util.regex.Matcher搜索字符串,而无需实现自己的搜索算法。
例如:
public class Main {
    public static void main(String[] args) {
        String[][] array2d = createArray();

        int charSeqColumn = 0;
        CharSequence charSequnce = new Array2DColumnCharSequnce(array2d, charSeqColumn);

        System.out.println(charSequnce.toString());

        Pattern patttern = Pattern.compile("ext");
        Matcher matcher = patttern.matcher(charSequnce);

        while (matcher.find()) {
            String matchGroup = matcher.group();
            int start = matcher.start();
            int end = matcher.end() - 1;

            String msg = MessageFormat.format("{0} matched at: [{1}] - [{2}]", matchGroup, start, end);
            System.out.println(msg);
        }
    }

    private static String[][] createArray() {
        String[][] array2d = new String[2][10];
        array2d[0][0] = "N";
        array2d[0][1] = "e";
        array2d[0][2] = "x";
        array2d[0][3] = "t";
        array2d[0][4] = " ";
        array2d[0][5] = "N";
        array2d[0][6] = "e";
        array2d[0][7] = "x";
        array2d[0][8] = "t";
        array2d[0][9] = " ";

        array2d[1][0] = "H";
        array2d[1][1] = "e";
        array2d[1][2] = "l";
        array2d[1][3] = "l";
        array2d[1][4] = "o";
        array2d[1][5] = "W";
        array2d[1][6] = "o";
        array2d[1][7] = "r";
        array2d[1][8] = "l";
        array2d[1][9] = "d";
        return array2d;
    }
}

将输出

Next Next 
ext matched at: [1] - [3]
ext matched at: [6] - [8]

我会这样实现CharSequence适配。
class Array2DColumnCharSequnce implements CharSequence {

    private int column;
    private String[][] array2d;
    private int endIndex;
    private int startIndex;

    public Array2DColumnCharSequnce(String[][] array2d, int column) {
        this(array2d, column, 0, array2d[column].length);
        this.array2d = array2d;
        this.column = column;
    }

    public Array2DColumnCharSequnce(String[][] array2d, int column,
            int startIndex, int endIndex) {
        this.array2d = array2d;
        this.column = column;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public int length() {
        return endIndex - startIndex;
    }

    public char charAt(int index) {
        String charString = array2d[column][startIndex + index];
        return charString.charAt(0);
    }

    public CharSequence subSequence(int start, int end) {
        Array2DColumnCharSequnce array2dColumnCharSequnce = new Array2DColumnCharSequnce(
                array2d, column, start, end);
        return array2dColumnCharSequnce;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(this);
        return sb.toString();
    }
}

注意:Array2DColumnCharSequence只是一个快速实现,它尚未处理异常情况,也没有处理字符串列中有多个字符的情况。

为什么要使用CharSequence装饰器

将数组适配为CharSequence的区别在于,您使用了一个标准的Java接口,可以与许多其他类一起重用,因此非常灵活。

一些经常使用CharSequence作为参数的标准Java类

点击这里查看完整列表。

使用上面的代码并尝试此操作,以查看修饰符有多灵活。

public static void main(String[] args) {
    String[][] array2d = createArray();

    CharSequence charSequnce = new Array2DColumnCharSequnce(array2d, 0);

    boolean contentEquals = "Next Next ".contentEquals(charSequnce);
    System.out.println(contentEquals);

    CharSequence column1CharSequnce = new Array2DColumnCharSequnce(array2d, 1);
    String replaced = "I want to say Next Next ".replace(charSequnce, column1CharSequnce);
    System.out.println(replaced);
}

将输出

true
I want to say HelloWorld

最终每个人都必须决定自己想要什么,以及什么更适合当前情况。如果可以几乎免费获得更多选项,则我更喜欢这种实现。


我该如何通过这种方式获取多个匹配字符串? - ductran
谢谢,我想知道我们是否需要一个CharSequence?我只是将我的第一列导出到一个字符串中,然后使用Matcher进行查找,就像@Trying所说的那样,这类似于在字符串中搜索子字符串。例如,我使用Matcher和正则表达式在abcdnextponexnextpour中搜索next并得到了相同的结果。你认为这种方法有什么问题吗? - ductran
@R4j 简短的回答是:我们不需要 CharSequence。我想展示一种面向对象的实现方式,我的方法是在二维数组上使用装饰器模式。这样做的唯一优点是我不需要创建一个新的字符串对象并复制字符。但就像我之前说的那样...我只是想展示一种面向对象的方式。我认为你的方法没有任何问题。 - René Link
如何检测字符的完整位置?例如“e匹配于[0][5]”或“f匹配于[1][8]”? - AloneInTheDark

1

这类似于在一个字符串中搜索子串。

例如:

A B C D N E X T J H  J  N   E   N   E   X   T   O 

0 1 2 3 4 5 6 7 8 9 10  11  12  13  14  15  16  17

所以答案应该是[4-7][13-16]
public static List<Integer> findIndexes(String source, String toFind){
    List<Integer> list = new LinkedList<Integer>();//it will return the starting indexes of the found substring, we can easily find the end e=index by adding the length of the other. 
    int start = 0;
    while(start < source.length()){
        if(source.charAt(start)==toFind.charAt(0)){//if the char is same then find whether the whole toFind string is present or not.
            if(isMatch(source, toFind, start)){//if it is found than increment the source pointer to the end after the toFind string
                list.add(start);
                start = start+toFind.length();
                continue;
            }
        }
        start++;
    }
    return list;
}
private static boolean isMatch(String s1, String s2, int srcIndex){
    int desIndex = 0;
    while(desIndex<s2.length() && s1.charAt(srcIndex)==s2.charAt(desIndex)){
        srcIndex++;
        desIndex++;
    }
    if(desIndex==s2.length()){
        return true;
    }
    return false;
}

还有一个示例驱动程序:

public static void main(String[] args) {    
        String s1="abcdnextponexnextpour";
        String s2 = "next";
        List<Integer> list = findIndexes(s1, s2);
        for(int i : list){
            System.out.println(i);
        }
    }

它将输出索引:
4
13

即,您可以添加toFind字符串的长度来计算最后一个索引。

0

我会按照以下方式实现search -

public static List<Interval> search(
    String searchText, String[][] data) {
  List<Interval> al = new ArrayList<>();
  if (searchText != null) {
    searchText = searchText.trim().toUpperCase();
    char[] toMatch = searchText.toCharArray();
    for (int i = 0; i < data.length; i++) {
      if (data[i] != null && data.length > i
          && data[i].length > 0
          && data[i][0].charAt(0) == toMatch[0]) {
        boolean matched = true;
        for (int t = 1; t < toMatch.length; t++) {
          if (i + t > data.length
              || data[i + t][0].charAt(0) != toMatch[t]) {
            i += (t - 1);
            matched = false;
            break;
          }
        }
        if (matched) {
          Interval interval = new Interval();
          interval.start = i - 1;
          interval.end = interval.start + (toMatch.length - 1);
          al.add(interval);
        }
      }
    }
  }
  return al;
}

我会修改Interval类,添加一个像这样的toString()方法

public String toString() {
  return String.valueOf(start) + "-" + end;
}

最后,为了测试它,我会使用这个主方法。
public static void main(String[] args) {
  String[][] test = { { "N" }, { "A" }, { "N" },
      { "A" }, { "T" }, { "A" }, { "N" }, { "E" },
      { "X" }, { "T" }, { "E" }, { "R" }, { "N" },
      { "B" }, { "N" }, { "E" }, { "X" }, { "T" } };
  List<Interval> al = search("next", test);
  for (Interval i : al) {
    System.out.println(i);
  }
}

我确实收到了这个输出 -

5-8
13-16

0

这是您的解决方案:

   void main(String a[][],String k){
   String m="";
   for(int i=0;i<a.length;i++)
   m+=a[i][0];
   int n=0,x;
   while(n<m.length()){
   n=m.indexOf(k,n);
   x=n+k.length();
   System.out.println(n+"-"+x);
   n=x;
   }
   }
   void main(String a[][],char k){
   for(int i=0;i <a.length;i++)
   if(a[i][0]==k)System.out.println(i);
   }

它提取dda的第一个字符串并进行搜索。 您可以生成值n和x作为类间隔,并将其包含在列表中。


这种方法并不适用于所有情况,例如,当我只搜索一个字符时,它会运行无限循环。 - ductran

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接