大文件查找 ( 积分: 50 )

W

weiqk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-04-25

• #1

我有一个大文件，大约200M，我想在其中查找某个单词，正则搜索，文件是单词列表，按照字母顺序排好序的，我想单独查找某个单词是很容易的，使用二分法查找，但问题的关键是我怎么定位到文件的某一行，怎样取得文件行数，文件是文本格式。

以上为问题之一，如果我用正则匹配某个单词，显然二分查找已经失去作用了，我才能提高效率？
谢谢大家，如果分不够另外开帖给分

 

白

白河愁

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-04-30

• #2

文本文件?还要按行分?再快也有限.

 

J

jenhon

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-04-30

• #3

200M的文本文件？ 想不出怎么维护这个文件。

为什么要取得行数呢？
要取整行内容的话就前后找一下回车，感觉比较快。

如果确实要找出具体的行数的话，建议自己加索引，比如在文件位置50M的地方是XXX行，然后找到你的词比较一下位置，就知道大概那一行后面，接着就是找回车符了，数一下应该很快，索引建密一点应该更快。
但是你每次更新文本，你就要维护索引文件，不是轻松的活啊。

 

W

weiqk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-05-04

• #4

因为文件中单词是排好序的，所以能利用二分法快速查找但是问题是用二分法查找怎样定位到某一行，这个是问题之关键

 

W

weiqk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-05-04

• #5

还有就是正则匹配，恐怕真的只有全文匹配了，或者我需要给文件做个索引，同志们帮我吧，这个问题困扰我两个月了，还真是不好解决

结贴的时候我会另外开帖送分

 

J

jenhon

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-05-07

• #6

全文正则匹配 有点超过谈论范围，索引恐怕不是人做的，至少我觉得很恐怖。

如果是纯英文搜索，可以考虑索引从 2字词 3字词 4字词.....建立起来，这样就有办法匹配到：and->stand land 这样的字样。
但搞不好索引比对象文件还大.....

究竟想做什么，能不能说明白点。
不能倒到数据库中去搜索？（不过也未必能提高效率，200M应该几千万的词量）

 

W

weiqk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-05-07

• #7

200M大约有500万词汇量的样子，网上有说法，说是排好序不等长的记录先索引，然后再二分查找，我不是很明白，哪位前辈能说明白些，怎么建索引，我不是科班出生，现在牵涉到算法和数据结构的东西很头痛，一定要想办法补起来

 

J

jenhon

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-05-07

• #8

给个具体的例子比较好说，要不还是不清楚你想要什么。
比如词库：

a
an
and
band
be
bee
bend
...

打个比方
问题一：现在是不是要找出bee的行数？

问题二：正则匹配，找出“所有”（？）包含 nd 的词汇？ 还有位置？ 行数？

（最好能够贴一点你的词库，大家一起学习）

 

W

wzquan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-05-07

• #9

文本格式不太好弄。我转换过别人的词库，好像是轻轻松松背单词的词库。他采用的是自定义数据库格式的。
最好自定义词库格式，每个字母后面加上索引，找的时候直接找索引序号就可以了。

 

W

weiqk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-05-08

• #10

crudware
cruft
cruft together
cruftsmanship
crufty
crumb
crunch
cryppie
CTSS
cube
cubing
cup holder
cursor dipped in X
cuspy
cut a tape
cybercrud
cyberpunk
cyberspace
cycle
cycle crunch
cycle drought
cycle of reincarnation
cycle server
cypherpunk
D. C. Power Lab

上面就是我的文件格式，单词是排好序的
也就是单词列表
当然可能是中文韩文日文俄罗斯语什么的，使用UTF-8编码
比如我想查找crunch怎么做呢，再比如我要查找cycle开头的单词，怎么做呢，关键是有200M的大文件，一行一行的读肯定是不行的

这个帖子的分太少了，事情做玩之后我会开帖另外送300分

 

J

jenhon

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-05-09

• #11

我觉得索引是不是可以用表来储存？

1、建立（维护）索引：
打开TXT，一行一行读，同时记住行号，如果当前的内容第一个字母（或者前2位、前3位）与前面的不一样，就把字母、行号、文件位置 写入表里（或者文件）；
内容大概是：
字母 行数 位置
A, 1 1
B, 50 250
C, 100 700
....
或者
A , 1 1
A A, 2 5
A B, 6 25
...
ARC 100 500
...
BAL 1000 5000
BAM 4000 20000
.....

2、使用索引：
切断或者加长你要查的单词，使到跟索引表用的字长一样，打开索引表（就几百到几万行），直接搜索第一个匹配的字母（或组合），取得大文件的对应起始位置，同时记下 下一个索引的起始位置。

然后打开大文件，移动指针，到刚取到的起始位置，一行一行地读，一边读一边加行数，这个动作应该很快，跟文件大小关系不大。读到符合的行就记录行数 和 单词组合。

循环读到下一个索引的位置停止，读出来数组应该就是你想要的吧。

就是这些，别怕困难，做起来很简单的。

 

W

weiqk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-05-09

• #12

结贴了，显然没有得到我想要的答案
非常jenhon无私的帮助