您所在位置：主题：huffman树和貌似简易搜索引擎的问题
icetommy
[专家分：0] 发布于 2007-02-05 16:27:00
老大们给个思路吧
根据Huffman算法编写一个对文件进行压缩和解压缩的程序。该程序可以对所有的文件类型进行压缩，压缩之后的文件后缀名为huff。同时，该程序可以对所有后缀名为huff的压缩文件进行解压缩。为了保存原来的文件名信息，使用该程序压缩之后的文件名应为`原来的文件名（包括后缀名）+ .huff ’。
例如：对文件名为 MyFile.exe进行压缩，则得到的压缩之后的文件名为：MyFile.exe.huff；相应的，对MyFile.exe.huff进行解压缩之后得到的文件名应该是：MyFile.exe。
该程序在压缩时，以字节为单位。由于一个字节最多可以表示256个不同的数据，所以可以根据字节所表示的数据值来表示Huffman算法的符号源，则最多有256个符号源。根据Huffman算法，对每个符号源根据其出现的频率进行可变长编码。
该程序支持下面的操作：
§ 压缩： Huffman -encode filename
§ 解压缩 ：Huffman –decode filename
为了使该程序具有通用性，压缩文件必须按照下面的格式存储。
§ 按照符号源值的升序排列，给出其相应的huffman编码串的长度（每个符号源1个字节，如果某个符号没有出现，则其huffman编码串的长度为0）
§ 符号源的huffman编码串（按照上面的符号源的顺序，二进制格式）
§ 表示源文件的长度（以字节为单位）的所需的字节个数（1个字节）
§ 源文件的长度（以字节为单位）（字节的个数等于上面的字节中的数据值）
§ 压缩后的数据（二进制格式）
对上面提到的格式进行简单的说明。
【采用16进制编辑器，如ultraedit，以二进制的格式打开源文件】
源文件的内容为：Hello World! （注：Hello和World中间的是一个Tab键）
16进制的内容为：48 65 6C 6C 6F 09 57 6F 72 6C 64 21
在这个文件中，对各个符号进行统计、编码，可以得到下表中的数据：
符号源的数据值（16进制） 出现频率 Huffman编码
09 1 1110
21 1 1111
48 1 1100
57 1 1101
64 1 0110
65 1 0111
6C 3 10
6F 2 00
72 1 010
根据上面的相应数据，可以得到对该文件进行Huffman压缩后，各个字段的数据值（为了能够形象的看到数据的表示，两个字节用|分割）
按照符号源的值升序排列其相应的huffman编码的长度：
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 2
0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
符号源的huffman编码串：11101111|11001101|01100111|1000010x
表示源文件的长度（以字节为单位）的字节个数：1
源文件的长度：12
压缩后的数据：11000111|10100011|10110100|01010011|01111xxx
【注意】当二进制串的个数不是8（字节的位数）的整数倍时，需要用0进行填充，上面的x表示的就是填充的数据位。
按照压缩文件的格式，最终的压缩文件应该是：（用16进制表示）
00 00 00 00 00 00 00 00 00 04 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 04 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00
00 00 00 00 00 00 00 04 00 00 00 00 00 00 00 00
00 00 00 00 04 04 00 00 00 00 00 00 02 00 00 02
00 00 03 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
EF CD 67 84 01 0C C7 A3 B4 53 78
【特别注意】压缩文件的格式是二进制，不要表示成二进制字符串，也不要表示成16进制的字符串。
【另外】在实验报告中要给出文件的大小和压缩、解压缩的时间关系。同时以表格和曲线图的形式提供实验数据。
尽可能的提高程序的性能，减少压缩/解压缩的时间，增加能够处理的文件的大小。
8、搜索引擎
作一个精简版本的google搜索引擎，该搜索引擎可以很好的利用地理位置信息。用户所处的位置可以通过多种方式获得，如IP地址，GPS定位等。为了简化，对于用户所处的位置可以通过交互的方式随机指定，即可以用（x，y）的方式给出用户所在的位置。另外，搜索的范围也可以通过交互的方式随机指定，如搜索半径为r。
在这个软件中，必须有一个地理位置数据库（文件），该数据库中包含了可供搜索的内容、相应的关键字以及必要的位置信息（x，y）。该数据库由我们自己提供，但要按照下面的格式来表示。
每条信息内容占一行，按照下面的格式：信息的ID（整个数据库唯一），分隔符（###），信息的名称，分隔符，信息的地址位置信息x，分隔符，y，分隔符，关键字1，分隔符，关键字2，分隔符，… ，分隔符，关键字N。信息的ID由系统自动生成，且大于0的整数表示。
该软件提供一个交互式图形界面，按照如下的方式启动：Google -f filename。其中filename给出按照上面的格式表示的地理位置数据库（文件）。程序在读取数据库文件的时候要检查给出的内容及相关信息的合法性，如果不合法，则忽略该条信息内容。
该软件使用关键字或者关键字表达式（AND，OR，NOT）进行搜索。由于关键字可以是一个字或者词，所以在需要的时候，可以使用“”””来表示一个词。例如：”java swing”表示在一个关键字中，java和swing两个字同时出现，且按照先后顺序出现。区别于java AND swing。
为了进行复杂的关键字表达式查询，表达式可以用“（）”来表示一定的组合关系。如：java AND (swing OR awt) 表示在一个关键字中，java必须和swing或者awt中的一个同时出现。下面对几个表达式运算符进行简单说明：
l AND，两个关键字、词同时出现。Key1 AND key2 表示key1和key2必须同时出现某信息的关键字列表中；
l OR，两个关键字、词有一个出现就可以。Key1 OR key2表示key1和key2至少有一个必须出现某信息的关键字列表中；
l NOT，关键字、词不能出现；NOT key1表示key1不能出现某信息的关键字列表中；
l （），组合关键字表达式，体现出关键字表达式的优先级组合关系。
当找到符合查询条件的信息时，如果仅有1条信息符合查询条件，则按照下面的格式给出：信息的ID，信息的名称，信息的位置（x，y）；如果有多条信息符合查询条件，则需要根据信息的位置信息由近及远按照升序排列之后再给出结果。
距离的计算可以采用下面的公式：
其中，xuser，yuser表示用户的位置，xinfo，yinfo表示信息的位置。
[em10]
根据Huffman算法编写一个对文件进行压缩和解压缩的程序。该程序可以对所有的文件类型进行压缩，压缩之后的文件后缀名为huff。同时，该程序可以对所有后缀名为huff的压缩文件进行解压缩。为了保存原来的文件名信息，使用该程序压缩之后的文件名应为`原来的文件名（包括后缀名）+ .huff ’。
例如：对文件名为 MyFile.exe进行压缩，则得到的压缩之后的文件名为：MyFile.exe.huff；相应的，对MyFile.exe.huff进行解压缩之后得到的文件名应该是：MyFile.exe。
该程序在压缩时，以字节为单位。由于一个字节最多可以表示256个不同的数据，所以可以根据字节所表示的数据值来表示Huffman算法的符号源，则最多有256个符号源。根据Huffman算法，对每个符号源根据其出现的频率进行可变长编码。
该程序支持下面的操作：
§ 压缩： Huffman -encode filename
§ 解压缩 ：Huffman –decode filename
为了使该程序具有通用性，压缩文件必须按照下面的格式存储。
§ 按照符号源值的升序排列，给出其相应的huffman编码串的长度（每个符号源1个字节，如果某个符号没有出现，则其huffman编码串的长度为0）
§ 符号源的huffman编码串（按照上面的符号源的顺序，二进制格式）
§ 表示源文件的长度（以字节为单位）的所需的字节个数（1个字节）
§ 源文件的长度（以字节为单位）（字节的个数等于上面的字节中的数据值）
§ 压缩后的数据（二进制格式）
对上面提到的格式进行简单的说明。
【采用16进制编辑器，如ultraedit，以二进制的格式打开源文件】
源文件的内容为：Hello World! （注：Hello和World中间的是一个Tab键）
16进制的内容为：48 65 6C 6C 6F 09 57 6F 72 6C 64 21
在这个文件中，对各个符号进行统计、编码，可以得到下表中的数据：
符号源的数据值（16进制） 出现频率 Huffman编码
09 1 1110
21 1 1111
48 1 1100
57 1 1101
64 1 0110
65 1 0111
6C 3 10
6F 2 00
72 1 010
根据上面的相应数据，可以得到对该文件进行Huffman压缩后，各个字段的数据值（为了能够形象的看到数据的表示，两个字节用|分割）
按照符号源的值升序排列其相应的huffman编码的长度：
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 2
0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
符号源的huffman编码串：11101111|11001101|01100111|1000010x
表示源文件的长度（以字节为单位）的字节个数：1
源文件的长度：12
压缩后的数据：11000111|10100011|10110100|01010011|01111xxx
【注意】当二进制串的个数不是8（字节的位数）的整数倍时，需要用0进行填充，上面的x表示的就是填充的数据位。
按照压缩文件的格式，最终的压缩文件应该是：（用16进制表示）
00 00 00 00 00 00 00 00 00 04 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 04 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00
00 00 00 00 00 00 00 04 00 00 00 00 00 00 00 00
00 00 00 00 04 04 00 00 00 00 00 00 02 00 00 02
00 00 03 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
EF CD 67 84 01 0C C7 A3 B4 53 78
【特别注意】压缩文件的格式是二进制，不要表示成二进制字符串，也不要表示成16进制的字符串。
【另外】在实验报告中要给出文件的大小和压缩、解压缩的时间关系。同时以表格和曲线图的形式提供实验数据。
尽可能的提高程序的性能，减少压缩/解压缩的时间，增加能够处理的文件的大小。
8、搜索引擎
作一个精简版本的google搜索引擎，该搜索引擎可以很好的利用地理位置信息。用户所处的位置可以通过多种方式获得，如IP地址，GPS定位等。为了简化，对于用户所处的位置可以通过交互的方式随机指定，即可以用（x，y）的方式给出用户所在的位置。另外，搜索的范围也可以通过交互的方式随机指定，如搜索半径为r。
在这个软件中，必须有一个地理位置数据库（文件），该数据库中包含了可供搜索的内容、相应的关键字以及必要的位置信息（x，y）。该数据库由我们自己提供，但要按照下面的格式来表示。
每条信息内容占一行，按照下面的格式：信息的ID（整个数据库唯一），分隔符（###），信息的名称，分隔符，信息的地址位置信息x，分隔符，y，分隔符，关键字1，分隔符，关键字2，分隔符，… ，分隔符，关键字N。信息的ID由系统自动生成，且大于0的整数表示。
该软件提供一个交互式图形界面，按照如下的方式启动：Google -f filename。其中filename给出按照上面的格式表示的地理位置数据库（文件）。程序在读取数据库文件的时候要检查给出的内容及相关信息的合法性，如果不合法，则忽略该条信息内容。
该软件使用关键字或者关键字表达式（AND，OR，NOT）进行搜索。由于关键字可以是一个字或者词，所以在需要的时候，可以使用“”””来表示一个词。例如：”java swing”表示在一个关键字中，java和swing两个字同时出现，且按照先后顺序出现。区别于java AND swing。
为了进行复杂的关键字表达式查询，表达式可以用“（）”来表示一定的组合关系。如：java AND (swing OR awt) 表示在一个关键字中，java必须和swing或者awt中的一个同时出现。下面对几个表达式运算符进行简单说明：
l AND，两个关键字、词同时出现。Key1 AND key2 表示key1和key2必须同时出现某信息的关键字列表中；
l OR，两个关键字、词有一个出现就可以。Key1 OR key2表示key1和key2至少有一个必须出现某信息的关键字列表中；
l NOT，关键字、词不能出现；NOT key1表示key1不能出现某信息的关键字列表中；
l （），组合关键字表达式，体现出关键字表达式的优先级组合关系。
当找到符合查询条件的信息时，如果仅有1条信息符合查询条件，则按照下面的格式给出：信息的ID，信息的名称，信息的位置（x，y）；如果有多条信息符合查询条件，则需要根据信息的位置信息由近及远按照升序排列之后再给出结果。
距离的计算可以采用下面的公式：
其中，xuser，yuser表示用户的位置，xinfo，yinfo表示信息的位置。
[em10]