java-在流中搜索字符串的有效方法

假设有一个文本流(或Java中的Reader),我想检查一个特定的字符串。 文本流可能非常大,因此,一旦找到搜索字符串,我想返回true,并且还尝试避免将整个输入存储在内存中。

天真的,我可能会尝试执行以下操作(在Java中):

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    while((numCharsRead = reader.read(buffer)) > 0) {
        if ((new String(buffer, 0, numCharsRead)).indexOf(searchString) >= 0)
            return true;
    }
    return false;
}

当然,如果它出现在1k缓冲区的边界上,则无法检测到给定的搜索字符串:

搜索文本:“ stackoverflow”
流缓冲区1:“ abc .........堆栈”
流缓冲区2:“溢出....... xyz”

如何修改此代码,以便它可以跨缓冲区边界正确找到给定的搜索字符串,而又不会将整个流加载到内存中?

编辑:请注意,在流中搜索字符串时,我们试图最小化从流中读取的次数(以避免网络/磁盘中的延迟),并使内存使用率保持恒定,而不管流中的数据量如何。 字符串匹配算法的实际效率是次要的,但是显然,找到使用这些算法中效率更高的一种的解决方案将是一个不错的选择。

Alex Spurling asked 2020-02-08T03:00:54Z
15个解决方案
13 votes

这里有三个好的解决方案:

  1. 如果您想要简单且相当快的东西,请不要使用任何缓冲区,而应实现一个简单的不确定性有限状态机。 您的状态将是要搜索的字符串的索引列表,并且您的逻辑看起来像这样(伪代码):

    n

    这将找到字符串(如果存在),而您将永远不需要缓冲。

  2. 工作量稍多,但速度也更快:执行NFA到DFA的转换,以预先找出可能的索引列表,并将每个索引分配给一个小整数。 (如果您在Wikipedia上阅读过有关字符串搜索的内容,则称为powerset构造。)然后您将具有一个状态,并对每个传入字符进行状态到状态的转换。 您想要的NFA只是字符串的DFA,其前面带有不确定地丢弃字符或尝试使用当前字符的状态。 您还需要一个明确的错误状态。

  3. 如果您想要更快的速度,请创建一个大小至少为n的缓冲区,然后用Boyer-Moore编译needle中的状态机。您会遇到很多麻烦,因为Boyer-Moore的实现并非易事(尽管 您将在网上找到代码),并且因为必须安排将字符串滑过缓冲区。 您将必须构建或找到一个可以“滑动”而不进行复制的循环缓冲区。 否则,您可能会从Boyer-Moore那里获得任何性能提升。

Norman Ramsey answered 2020-02-08T03:01:51Z
11 votes

对于部分搜索,我对Knuth Morris Pratt算法做了一些更改。 由于实际的比较位置始终小于或等于下一个位置,因此不需要额外的存储空间。 带有Makefile的代码也可以在github上找到,并且用Haxe编写,可以同时针对多种编程语言,包括Java。

我还写了一篇相关文章:在流中搜索子字符串:Haxe中对Knuth-Morris-Pratt算法的略微修改。 文章提到了雅加达RegExp,现在已经退休并在Apache Attic中休息。 RE类中的Jakarta Regexp库“ match”方法使用CharacterIterator作为参数。

class StreamOrientedKnuthMorrisPratt {
    var m: Int;
    var i: Int;
    var ss:
    var table: Array<Int>;

    public function new(ss: String) {
        this.ss = ss;
        this.buildTable(this.ss);
    }

    public function begin() : Void {
        this.m = 0;
        this.i = 0;
    }

    public function partialSearch(s: String) : Int {
        var offset = this.m + this.i;

        while(this.m + this.i - offset < s.length) {
            if(this.ss.substr(this.i, 1) == s.substr(this.m + this.i - offset,1)) {
                if(this.i == this.ss.length - 1) {
                    return this.m;
                }
                this.i += 1;
            } else {
                this.m += this.i - this.table[this.i];
                if(this.table[this.i] > -1)
                    this.i = this.table[this.i];
                else
                    this.i = 0;
            }
        }

        return -1;
    }

    private function buildTable(ss: String) : Void {
        var pos = 2;
        var cnd = 0;

        this.table = new Array<Int>();
        if(ss.length > 2)
            this.table.insert(ss.length, 0);
        else
            this.table.insert(2, 0);

        this.table[0] = -1;
        this.table[1] = 0;

        while(pos < ss.length) {
            if(ss.substr(pos-1,1) == ss.substr(cnd, 1))
            {
                cnd += 1;
                this.table[pos] = cnd;
                pos += 1;
            } else if(cnd > 0) {
                cnd = this.table[cnd];
            } else {
                this.table[pos] = 0;
                pos += 1;
            }
        }
    }

    public static function main() {
        var KMP = new StreamOrientedKnuthMorrisPratt("aa");
        KMP.begin();
        trace(KMP.partialSearch("ccaabb"));

        KMP.begin();
        trace(KMP.partialSearch("ccarbb"));
        trace(KMP.partialSearch("fgaabb"));

    }
}
sw. answered 2020-02-08T03:01:08Z
8 votes

Knuth-Morris-Pratt搜索算法永远不会备份。 这只是您要用于流搜索的属性。 尽管使用可用的Java库可能有更简便的方法,但我之前曾用过它。 (当出现这种情况时,我在90年代在C中工作。)

本质上,KMP是构建字符串匹配DFA的快速方法,例如Norman Ramsey的建议2。

Darius Bacon answered 2020-02-08T03:02:16Z
5 votes

此答案适用于问题的初始版本,在该版本中,关键是仅在与字符串匹配时(如果存在)读取流。 此解决方案不能满足保证固定内存使用率的要求,但是如果您发现了这个问题并且不受此约束的约束,则可能值得考虑。

如果您受到恒定内存使用约束的约束,那么Java将任何类型的数组存储在堆上,因此,将引用设为空不会以任何方式取消分配内存; 我认为任何在循环中涉及数组的解决方案都会消耗堆内存,并需要GC。


对于简单的实现,也许Java 5的Scanner可以接受InputStream并使用java.util.regex.Pattern来搜索输入,以免您担心实现细节。

这是一个潜在实现的示例:

public boolean streamContainsString(Reader reader, String searchString)
            throws IOException {
      Scanner streamScanner = new Scanner(reader);
      if (streamScanner.findWithinHorizon(searchString, 0) != null) {
        return true;
      } else {
        return false;
      }
}

我在考虑正则表达式,因为这听起来像是有限状态自动机的工作,它从初始状态开始,逐个字符地更改状态,直到拒绝字符串(不匹配)或进入接受状态为止。

我认为这可能是您可以使用的最有效的匹配逻辑,并且可以将组织信息读取的方式与匹配逻辑分开,以进行性能调整。

这也是正则表达式的工作方式。

brabster answered 2020-02-08T03:03:04Z
4 votes

不要将缓冲区作为数组,而应使用实现循环缓冲区的抽象。 您的索引计算将为buf[(next+i) % sizeof(buf)]048,并且您必须小心一次将缓冲区填满一半。 但是,只要搜索字符串适合缓冲区的一半,就可以找到它。

Norman Ramsey answered 2020-02-08T03:03:24Z
4 votes

我认为,解决此问题的最佳方法是设法使其简单。 记住,因为我正在从流中读取数据,所以我希望将流中的读取次数保持最少(因为网络或磁盘延迟可能是一个问题),同时保持使用的内存量不变(因为流可能是 非常大)。 字符串匹配的实际效率不是第一个目标(因为已经研究到死了)。

根据AlbertoPL的建议,这是一个简单的解决方案,将缓冲区与搜索字符串的每个字符进行比较。 关键在于,由于一次只搜索一个字符,因此不需要回溯,因此不需要循环缓冲区或特定大小的缓冲区。

现在,如果有人可以提出基于Knuth-Morris-Pratt搜索算法的类似实现,那么我们将有一个很好的有效解决方案;)

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    int count = 0;
    while((numCharsRead = reader.read(buffer)) > 0) {
        for (int c = 0; c < numCharsRead; c++) {
            if (buffer[c] == searchString.charAt(count))
                count++;
            else
                count = 0;
            if (count == searchString.length()) return true;
        }
    }
    return false;
}
Alex Spurling answered 2020-02-08T03:03:54Z
2 votes

从Ujorm框架的RingBuffer类中实现了对流的非常快速的搜索。 参见示例:

 Reader reader = RingBuffer.createReader("xxx ${abc} ${def} zzz");

 String word1 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("abc", word1);

 String word2 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("def", word2);

 String word3 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("", word3);

单个类的实现在SourceForge上可用:有关更多信息,请参见链接。

pop answered 2020-02-08T03:04:18Z
1 votes

实现一个滑动窗口。 围绕缓冲区,向前移动缓冲区中的所有元素,最后在缓冲区中输入一个新字符。 如果缓冲区等于搜索到的单词,则包含该缓冲区。

当然,如果您想提高效率,可以考虑一种方法来防止移动缓冲区中的所有元素,例如通过使用循环缓冲区和表示字符串的方式“循环”缓冲区 这样做,所以您只需要检查内容是否相等。 这样可以节省缓冲区中所有元素的移动。

Tetha answered 2020-02-08T03:04:43Z
1 votes

我认为您需要在缓冲区之间的边界处缓冲少量缓冲区。

例如,如果您的缓冲区大小为1024,而SearchString的长度为10,则除了搜索每个1024字节的缓冲区之外,您还需要搜索两个缓冲区之间的每个18字节过渡(从上一个缓冲区的末尾起9个字节) 从下一个缓冲区的开头起9个字节串联在一起)。

ChrisW answered 2020-02-08T03:05:08Z
1 votes

我会说切换到一个字符一个字符的解决方案,在这种情况下,您将扫描目标文本中的第一个字符,然后当您发现该字符时增加一个计数器并寻找下一个字符。 每次找不到下一个连续字符时,都要重新启动计数器。 它将像这样工作:

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
char[] buffer = new char[1024];
int numCharsRead;
int count = 0;
while((numCharsRead = reader.read(buffer)) > 0) {
    if (buffer[numCharsRead -1] == searchString.charAt(count))
        count++;
    else
        count = 0;

    if (count == searchString.size())    
     return true;
}
return false; 
}

唯一的问题是当您正在浏览字符时……在这种情况下,需要一种记住计数变量的方法。 除了作为整个类的私有变量外,我看不到这样做的简单方法。 在这种情况下,您将不会在此方法内实例化计数。

AlbertoPL answered 2020-02-08T03:05:33Z
1 votes

如果您不希望使用阅读器,那么可以使用Java的NIO API高效地加载文件。 例如(未经测试,但应接近工作状态):

public boolean streamContainsString(File input, String searchString) throws IOException {
    Pattern pattern = Pattern.compile(Pattern.quote(searchString));

    FileInputStream fis = new FileInputStream(input);
    FileChannel fc = fis.getChannel();

    int sz = (int) fc.size();
    MappedByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, sz);

    CharsetDecoder decoder = Charset.forName("UTF-8").newDecoder();
    CharBuffer cb = decoder.decode(bb);

    Matcher matcher = pattern.matcher(cb);

    return matcher.matches();
}

基本上,mmap()是要搜索的文件,并依赖操作系统来做有关缓存和内存使用的正确操作。 但是请注意,仅将文件读入较大的缓冲区(小于10 KiB左右的文件)时,map()会更昂贵。

deverton answered 2020-02-08T03:05:58Z
1 votes

您可能可以使用快速傅立叶变换来实现非常快速的解决方案,如果实施得当,它可以使您在时间O(nlog(m))中进行字符串匹配,其中n是要匹配的较长字符串的长度, m是较短字符串的长度。 例如,您可以在收到长度为m的流输入后立即执行FFT,如果匹配,则可以返回,如果不匹配,则可以丢弃流输入中的第一个字符,请等待 让新字符在流中出现,然后再次执行FFT。

rboling answered 2020-02-08T03:06:19Z
0 votes

您可以通过使用某些字符串搜索算法来提高搜索非常大的字符串的速度

Alex answered 2020-02-08T03:06:38Z
0 votes

如果您要查找常量子字符串而不是正则表达式,则建议使用Boyer-Moore。 互联网上有很多源代码。

另外,请使用循环缓冲区,以避免过分考虑缓冲区边界。

麦克风。

answered 2020-02-08T03:07:07Z
0 votes

我也有一个类似的问题:从InputStream跳过字节,直到指定的字符串(或字节数组)。 这是基于循环缓冲区的简单代码。 它不是很有效,但是可以满足我的需求:

  private static boolean matches(int[] buffer, int offset, byte[] search) {
    final int len = buffer.length;
    for (int i = 0; i < len; ++i) {
      if (search[i] != buffer[(offset + i) % len]) {
        return false;
      }
    }
    return true;
  }

  public static void skipBytes(InputStream stream, byte[] search) throws IOException {
    final int[] buffer = new int[search.length];
    for (int i = 0; i < search.length; ++i) {
      buffer[i] = stream.read();
    }

    int offset = 0;
    while (true) {
      if (matches(buffer, offset, search)) {
        break;
      }
      buffer[offset] = stream.read();
      offset = (offset + 1) % buffer.length;
    }
  }
dmitriykovalev answered 2020-02-08T03:07:27Z
translate from https://stackoverflow.com:/questions/846175/efficient-way-to-search-a-stream-for-a-string