1

我有一个制表符分隔的 UTF-8 文件，其中记录按一个字段排序。但是，线的大小不是固定的，所以不能直接跳到特定的位置。如何对此执行二进制搜索？

例子：

第 1 行：阿尔弗雷德·布伦德尔 /m/011hww /m/0crsgs6,/m/0crvt9h,/m/0cs5n_1,/m/0crtj4t,/m/0crwpnw,/m/0cr_n2s,/m/0crsgyh

第 2 行：鲁珀特·谢尔德雷克 /m/011ybj /m/0crtszs

4

4 回答 4

3

你知道你的洞文件包含的字节数。让我们说n -> search-interval [l, r]with l=0, r=n。

  • 估计你的 search-interval 的中间值m=(r-l)/2。在这个位置向左移动尽可能多的字节（右边也可以），直到找到一个制表符（字节==9 （9 是制表符的 ASCII 和 UTF8 代码））[让我们命名这个位置mReal]并解码一行开始该选项卡。

  • 确定您是否必须在下一个搜索步骤中采用前一个“半”（=> 新搜索间隔是[l, mReal]）或第二个“半”（=> 新搜索间隔是[mReal, r]）。

于 2013-01-16T15:57:46.830 回答
0 
public class YourTokenizer {

    public static final String EPF_EOL = "\t";

    public static final int READ_SIZE = 4 * 1024 ;

    /** The EPF stream buffer. */
    private StringBuilder buffer = new StringBuilder();

    /** The EPF stream. */
    private InputStream stream = null;

    public YourTokenizer(final InputStream stream) {
        this.stream = stream;
    }

    private String getNextLine() throws IOException {
        int pos = buffer.indexOf(EPF_EOL);
        if (pos == -1) {
            // eof-of-line sequence isn't available yet, read more of the file
            final byte[] bytes = new byte[READ_SIZE];
            final int readSize = stream.read(bytes, 0, READ_SIZE);


            buffer.append(new String(bytes));
            pos = buffer.indexOf(EPF_EOL);
            if (pos == -1) {
                if (readSize < READ_SIZE) {
                    // we have reached the end of the stream and what we're looking for still can't be found
                    throw new IOException("Premature end of stream");
                }
                return getNextLine();
            }
        }

        final String data = buffer.substring(0, pos);
        pos += EPF_EOL.length();
        buffer = buffer.delete(0, pos);
        return data;
    }

}

以 main 结尾：

final InputStream stream = new FileInputStream(file);
 final YourTokenizer tokenizer = new YourTokenizer(stream);

 String line = tokenizer.getNextLine();
 while(line != line) {
   //do something
   line = tokenizer.getNextLine();
 }
于 2013-01-16T16:05:44.723 回答
0

您可以跳转到字节的中间。从那里您可以找到该行的结尾，您可以从该点读取下一行。如果您需要向后搜索，则每次取四分之一点或四分之三并找到线。最终，您会将其缩小到一行。

于 2013-01-16T16:05:51.263 回答
0

我想你可以从文件大小中猜出行长

然而，当您甚至无法猜测线条的长度时，我认为最好选择生成随机数。

于 2013-01-16T15:59:55.413 回答