leelight
2009-11-06 04:21
浏览 256
已采纳

关于不读取 全部数据进内存的二分折半查找法的应用

编程语言用java
现在有一个字典数据文件,格式如下:
.........

就是一个单词+0x00 + int整形(4字节)+ int整形(4字节)
举例:
a 0x00 0x00 0x00 0x00 0x0a 0x00 0x00 0x00 0x2d aba 0x00 0x00 0x00 0x00 0x01 0x00 0x00 0x00 0x35......
字典按字母顺序已经排序。
如果把这些词全部读入内存,然后用二分折半查找其实很简单,现在问题是由于在手持设备上读取,不能全部读入内存再查找。如果不用二分法非常慢。
但是如果用了二分法,实时定位困扰我很久,一直无法解决。因为加入文件长20000,第一次定位在10000的位置,这个位置如果出现在string里面,那么继续往下读到0x00,就可以判断单词结束,继续往下读两个int即可。但是如果出现在int数据间,那就无法用0x00来作为分隔符了,因为int本身的四个byte就可能含0x00。z 这样我没法知道哪个位置开始是string。
如果用c,有个函数可以直接读byte,自动读取当前位置后面的string,但是java就没办法了。
数据文件结构不能更改,请教大家有没有什么巧妙的办法可以不读入内存直接二分法查询?
谢谢!
[b]问题补充:[/b]
我自己也也用了索引法,我是这么建索引的:

这里的int就是字典文件里string的offset,我是按头字母和每隔100个string采用一个作为索引,就是这样,索引文件还是有500kb,500kb对小型设备还是比较多。
我觉得肯定有更好的索引创建方法,比如先按第一个字母作索引,再按头两个字母做索引,不过还没想到怎么创建这个索引文件比较高效和尺寸小.

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • wertyu1 2009-11-06 09:30
    已采纳

    或者将索引写到一个临时文件里,先找索引,再找字符窜

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • wertyu1 2009-11-06 09:18

    能不能在内存中建一个字符窜起始位置索引

    评论
    解决 无用
    打赏 举报
  • Null_Shadow 2009-11-06 15:28

    顶cralcui, 内存中建立索引的方法是可取的,这样可以避免掉楼主的查找定位问题

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题