注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

Radix tree ? 和 倒排索引/反向索引(Inverted index) 做一道腾讯面试题  

2011-04-18 17:53:33|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

在网上看到一道听说是腾讯的php面试的题目,试着做了一下。用了这两个:

1. Radix tree    http://en.wikipedia.org/wiki/Radix_tree
   以前在同事桌子上的算法书上瞄了一眼。好像上面有个单词的每个字符作为一饿节点的图形。好像用来这里不错,希望我没记错。网站上说到,一个节点可以放几个字母组成的串的,那样可能更省空间吧。每个节点一个字母的应该叫做“单词查找树” trie data structure , http://en.wikipedia.org/wiki/Trie    .   Radix tree 是trie的空间优化形式。

2. 倒排索引        http://zh.wikipedia.org/wiki/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95
   之前看上面搜索引擎,看到这个次,应该就是这样子用的吧。

 

/*
编程任务:
1、我们碰到了大麻烦,一个新来的传教士惹恼了上帝,上帝很愤怒,要求我们把圣经(bbe.txt)背熟,直至他说哪个单词,我们就要飞快的回答出这个单词在第几行第几个单词位置。听说你是个优秀的程序员,那么髟助我们完成这个不可能的任务吧。
要求如下:
1)/myworks/example/bbe.txt,98版本英文圣经一本
2)输入部分要求如下:php ./example.php [单词]
3)输出部分如下:[单词] 1,2 2,4 5,6 表示:此单词在1行2列(第二个单词),2行4列...
说明:
1)此文本4MB之巨...
2)单词的含义:由英文字母(大小写),数字(0-9)组成的串
3)提供给你的机器OS为ubuntu 9.10,内存只有1G,而且,很不幸的,其中700M用来做了别的
4)上机考试不允许上网,但我装了man文档以及读取CHM以及PDF的阅读器,在电脑的桌面的CHM文件夹中,有相应的PHP参考手册
5)算法复杂度要求不能大于O(N^2)(就是N的平方)
6)什么?PHP低效且用起来不顺手,好的,你可以用别的语言来实现。但注意:提供给你的机器上只有python 2.4/perl 5.8/gcc[g++] 4.1
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct index_struct{
   int line;
   int offset;
   int next;
};

//4M * 40 =  160M 
typedef struct node_struct {
        struct node_struct * letter[26];
        struct node_struct  * digital[10];
        int index;
} Node;


static Node root;
static const int MAX_WORD_COUNT = 4 * 1024 * 1024/ 3;   //假设每个单词3个byte
static struct index_struct index_data[4 * 1024 * 1024/ 3];   //这块大概占16M
int start = 1;
int node_num = 0;

int is_letter( char x)
{
    return x >= 'a' && x <= 'z' || x >= 'A' && x <= 'Z';
}
 
int is_digital( char x)
{
    return x >= '0' && x <= '9';
}



int lookup( char * word )
{
     if ( word ==NULL) return -1;

     Node * node= &root;
    
     while (*word != '\0') {
           char x = *word;
           word ++;
           if (is_letter(x))
           {
                x =  tolower(x);
                if (node->letter[ x -'a'] == NULL)
                {
                    return -1;
                }
                node = node->letter[ x - 'a'];
           }else if (is_digital(x))
           {
                if (node->digital[ x - '0'] == NULL )
                {
                    return -1;
                }
                node = node->digital[ x - '0'];
           } else {
                   printf( "输入中包含非法字符: %c\n", x);
                   return  -1;
           }
     }    
    
     return node->index;
}

Node * alloc_node()
{
     Node * new_node = malloc(sizeof(Node));
     memset(new_node,0, sizeof(Node));
     node_num ++;
     return  new_node;
}

int insert( char * word, int line, int offset)
{
     if ( word ==NULL) return -1;
     //printf( "添加单词:%s, line=%d,offset=%d\n",word, line,offset);

     Node * node= & root;
    
     while (*word != '\0') {
           char x = *word;
           word ++;
           if ( is_letter(x))
           {
                x =  tolower(x);
                if (node->letter[x -'a'] == NULL )
                {
                    Node * new_node = alloc_node();
                    node->letter[ x -'a'] = new_node;
                    node = new_node;
                } else {
                       node = node->letter[ x - 'a'];
                }

           }else if (is_digital(x))
           {
                if (node->digital[ x -'0'] == NULL )
                {
                    Node * new_node = alloc_node();
                    node->digital[ x -'0'] = new_node;
                    node = new_node;
                }else {
                      node = node->digital[ x - '0'];
                }
           }       
    }  
   
   
    int i;
    if ( 0 == node->index) {
         node->index = ++start;
    } else {
         i = node->index;
         while (index_data[i].next != 0){
            i = index_data[i].next;
         }  
         index_data[i].next = ++start;
    }
       
    index_data[start].line = line;
    index_data[start].offset = offset;
    index_data[start].next =0;
   
    return 0;
}

void report(int i)
{
      while(i > 0){
            printf ("出现在第%d行,第%d个单词\n", index_data[i].line,  index_data[i].offset);
            i = index_data[i].next;
      }
      printf ("\n");
}

void scan (char * text , int line){
     char * word_start=NULL;
     int offset = 1;
     while (*text != '\n') {
          if (is_letter( * text) || is_digital( * text)){
                if (word_start ==NULL)
                       word_start = text;
          } else {
                if (word_start != NULL)
                {
                    *text = '\0';
                    insert(word_start,line,offset);
                    word_start=NULL;
                    offset ++;
                }
          }
          text ++;
    }
    
    if ( word_start !=NULL) {
          *text = '\0';               
          insert(word_start,line,offset);
          word_start=NULL;
          offset ++;   
    }
}

void load (char *filename)
{
     char * text =NULL;
     int line = 1;
     FILE * fp;
     size_t len = 0;
     ssize_t read;

     fp = fopen(filename, "r");
 
     while ((read = getline(&text, &len, fp)) != -1) {
          scan(text, line++);
     }
     if (text)
         free(text);

     fclose(fp);
    
     printf("node节点使用内存:%d M, index使用内存:%d M , 使用index项=%d 个\n", sizeof(Node) * node_num /(1024*1024),
                     sizeof(index_data) / (1024*1024) ,start);
    
}




int main(void)
{
    load( "bbe.txt");
    char word[16];
    printf("请输入要查询的单词:");
    while (scanf("%s",word)){
        int i = lookup(word);
        if (i > 0 ){
           report (i);
        } else {
              printf("没有这个单词的记录!\n");
        }
        printf("请输入要查询的单词:");
    }
    
    return 0;
}

 

 

 


Radix tree ? 和 倒排索引/反向索引(Inverted index) 做一道腾讯面试题 - widebright - widebright的个人空间

 

   在  http://ishare.iask.sina.com.cn/f/12042582.html 这里下载那个4M多的圣经原文,然后运行程序
widebright@gdeng:~/桌面$ ./a.out
node节点使用内存:2 M, index使用内存:15 M , 使用index项=941143 个
请输入要查询的单词:fuck
没有这个单词的记录!       Radix tree ? 和 倒排索引/反向索引(Inverted index) 做一道腾讯面试题 - widebright - widebright的个人空间  还是挺文明的嘛,一个也没有
请输入要查询的单词:love
出现在第510行,第26个单词
出现在第660行,第19个单词
出现在第688行,第7个单词
出现在第688行,第24个单词
出现在第783行,第14个单词
出现在第815行,第8个单词
出现在第817行,第16个单词
出现在第827行,第13个单词
出现在第827行,第20个单词
出现在第829行,第36个单词
...
出现在第30723行,第18个单词
出现在第30738行,第12个单词
出现在第30757行,第41个单词

请输入要查询的单词:mother
出现在第56行,第17个单词
出现在第77行,第18个单词
出现在第415行,第32个单词
.....
出现在第30197行,第14个单词
出现在第30982行,第16个单词
请输入要查询的单词:haha
没有这个单词的记录!

 

程序我就只能写到这种程度了吧,查询还是挺快的,内存也满足题目的要求吧。不过初始化扫描要花点时间。不知道还没有其他优化的空间,那位朋友想到的,提示一下吧。做这题明显花的不只1个小时阿,我太弱了!

  评论这张
 
阅读(882)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017