2011-01-19 121 views
1

我有40KB的HTML页面,我想找到它的某些模式。在长字符串中查找模式?

我可以通过1K缓冲区读取它,但我想避免这种情况,即我正在搜索的模式会在两个缓冲区读取之间分开。

如何克服这个问题?

回答

3

这很简单。您可以计算您要查找的最长模式,然后按照该数量回溯文件指针,或者滚动文件,只读取增量。

想象一下最长的模式是26个字节。

  1. 阅读1k。
  2. 检查所有模式 - >无。
  3. 从缓冲区中删除1k - 26个字节。
  4. 阅读1000 - 从物流26个字节,并添加到您的缓冲区
  5. 转到2.

编辑:让我澄清一下:有两种方法可以做到这一点,两者各有优劣。我上面记录的一个最适合用于从流中读取数据,这意味着不支持查找的数据源。但是,如果您的数据源确实支持寻找(如文件系统文件),那么您可以轻松地使用搜索。检查图案,如果找不到,请回溯最长图案的尺寸,然后从那里开始。

但是,如果您希望支持搜索长度超过缓冲区大小的模式,则可能需要更聪明的算法。您需要一个包含当前“打开”的所有模式的查阅表,以便读取更多数据,这反过来会花费更多的内存 - 您会遇到问题。

+0

让我们只希望他的长度最长的字符串不是1k-1 :) – 2011-01-19 15:14:20

+0

好主意,但它只适用于,如果他搜索确切的字符。如果模式 - 一些html标签之间的所有内容。它的长度是不可预测的。 – 2011-01-19 15:14:46

0

为什么不使用SAX parser。它是建立处理大型文件的标记。如果您尝试在同一级别的不同元素上进行匹配,您会遇到问题。然而,这不是不可能处理