c++ - 关于用C从txt文件查找单词的搜索算法优化问题

Question

用C或C++实现从一个比较大的txt文件里查找一个单词，txt文件里每行一个单词，按a~z从上到下排列，有什么好的算法，用什么数据结构可以提高查询的速度和效率？？

Answer 1

這種情況考慮下麵這種數據結構： 字典樹(DictTree)

typedef struct _dict_tree_
{
    struct _dict_tree_ * dt[TREENODENUM];
    char    c ;
    char    flag ;
}DT ;

具體操作就是

所謂的26叉樹，按照每個字母對應的子節點存儲。 然後逐行讀取單詞後插入到樹中，比如說： 單詞：abandon 插入樹的順序就是 a->b->a->n->d->o->n 插入每個字母對應這個樹的子節點

int len = strlen(str);
while( i < len )
{
    index = str[i] - 97 ;　　　　　　　　/*通过 index 来找到子节点*/
    if( pt->dt[index] == NULL )
    {
        pt->dt[index] = ( DT *)malloc( sizeof( DT) );
        pt->dt[index]->c = str[i] ;
        pt->dt[index]->flag = EMPTY ;
        for( j = 0 ; j < TREENODENUM ; j++ )
        {
            pt->dt[index]->dt[j] = NULL ;
        }
    }
    pt = pt->dt[index] ;
    i++;
}

查找就是順著字母判斷子節點是否為空

int len = strlen(str);
while( i != len )
{
    index = str[i] - 97 ;
    if( pt->dt[index] == NULL )
        return 0 ;
    pt = pt->dt[index] ;
    i++;
}

Answer 2

如果允許對txt文件預處理的話，可以用倒排索引來實現。

如果txt文件隻查一次、以後再也用不到的話，那就沒有。

Answer 3

按你的題目來看，似乎這些單詞都是排過序的？如果是有序的話，就可以按照二分的方法來做。先讀取文件總共由多少行，然後以第一個字符來查找，再按照第二個字符，以此類推，這個算法的好處是不用讀取所有文件到內存中。

Answer 4

如果修改一下問題，這個txt文件有1T大，怎麼弄會好點。聲望不夠，改不了。