C语言中压缩字符串的简单算法小结

2024-09-30 01:12:28

应用中，经常需要将字符串压缩成一个整数，即字符串散列。比如下面这些问题：
（1）搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。请找出最热门的10个检索串。
（2）有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
（3）有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
（4）给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url。
（5）一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词。

这些问题都需要将字符串压缩成一个整数，或者说是散列到某个整数 M 。然后再进行取余操作，比如 M%16，就可以将该字符串放到编号为M%16的文件中，相同的字符串肯定是在同一个文件中。通过这种处理，就可以将一个大文件等价划分成若干小文件，而对于小文件，就可以用常规的方法处理，内排序、hash_map等等。最后将这些小文件的处理结果综合起来，就可以求得原问题的解。
下面介绍一些字符串压缩的算法。

方法1：最简单就是将所有字符加起来，代码如下：

unsigned long HashString(const char *pString, unsigned long tableSize)
{
 unsigned long hashValue = 0;
 while(*pString)
    hashValue += *pString++;
 return hashValue % tableSize;
}

分析：如果字符串的长度有限，而散列表比较大的话，浪费比较大。例如，如果字符串最长为16字节，那么用到的仅仅是散列表的前16*127=2032。假如散列表含2729项，那么2032以后的项都用不到。

方法2：将上次计算出来的hash值左移5位（乘以32），再和当前关键字相加，能得到较好的均匀分布的效果。

unsigned long HashString(const char *pString,unsigned long tableSize)
{
 unsigned long hashValue = 0;
 while (*pString)
 hashValue = (hashValue << 5) + *pString++;
 return hashValue % tableSize;
}

分析：这种方法需要遍历整个字符串，如果字符串比较大，效率比较低。

方法3：利用哈夫曼算法，假设只有0-9这十个字符组成的字符串，我们借助哈夫曼算法，直接来看实例：

#define Size 10
int freq[Size];
string code[Size];
string word;
struct Node
{
 int id;
 int freq;
 Node *left;
 Node *right;
 Node(int freq_in):id(-1), freq(freq_in)
 {
  left = right = NULL;
 }
};
struct NodeLess
{
 bool operator()(const Node *a, const Node *b) const
 {
  return a->freq < b->freq;
 }
}; 

void init()
{
 for(int i = 0; i < Size; ++i)
  freq[i] = 0;
 for(int i = 0; i < word.size(); ++i)
  ++freq[word[i]];
}
void dfs(Node *root, string res)
{
 if(root->id >= 0)
  code[root->id] = res;
 else
 {
  if(NULL != root->left)
   dfs(root->left, res+"0");
  if(NULL != root->right)
   dfs(root->right, res+"1");
 }
} 

void deleteNodes(Node *root)
{
 if(NULL == root)
  return ;
 if(NULL == root->left && NULL == root->right)
  delete root;
 else
 {
  deleteNodes(root->left);
  deleteNodes(root->right);
  delete root;
 }
}
void BuildTree()
{
 priority_queue<Node*, vector<Node*>, NodeLess> nodes;
 for(int i = 0; i < Size; ++i)
 {
//0 == freq[i] 的情况未处理
    Node *newNode = new Node(freq[i]);
  newNode->id = i;
  nodes.push(newNode);
 }
 while(nodes.size() > 1)
 {
  Node *left = nodes.top();
  nodes.pop();
  Node *right = nodes.top();
  nodes.pop();
  Node *newNode = new Node(left->freq + right->freq);
    newNode->left = left;
    newNode->right = right;
    nodes.push(newNode);
 }
 Node *root = nodes.top();
 dfs(root, string(""));
 deleteNodes(root);
}

C语言字符串原地压缩实现方法

本文实例讲述了C语言字符串原地压缩的实现方法,对于学习字符串操作的算法设计有不错的借鉴价值.分享给大家供大家参考.具体方法如下: 字符串原地压缩示例: "eeeeeaaaff"压缩为"e5a3f2" 具体功能代码如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> #include <iterator> #include <
C语言文件操作函数大全(超详细)

fopen(打开文件)相关函数 open,fclose表头文件 #include<stdio.h>定义函数 FILE * fopen(const char * path,const char * mode);函数说明参数path字符串包含欲打开的文件路径及文件名,参数mode字符串则代表着流形态.mode有下列几种形态字符串:r 打开只读文件,该文件必须存在.r+ 打开可读写的文件,该文件必须存在.w 打开只写文件,若文件存在则文件长度清为0,即该文件内容会消失.若文件不存在则建立该文件.w
C语言实现修改文本文件中特定行的实现代码

好的,首先我先叙述下功能要求:其实很简单,就是Shell中sed命令的C语言实现,实现定位到所需要的字段的那一行,之后修改成需要的内容.但是由于C语言是面向过程的语言,需要顺序执行的特点,所以,实现中遇到了很多麻烦,在这里博主将实现的过程描述如下,以便大家参考. 问题描述: 文本内容: 复制代码代码如下: wireless.1.authmode=1wireless.1.compression=0wireless.1.current_ap=ssid12wireless.1.current_sta
C语言压缩文件和用MD5算法校验文件完整性的实例教程

使用lzma SDK对7z文件简单解压缩有时候我们只需要单纯对lzma算法压缩的7z文件进行解压,有时需要在嵌入式设备上解压,使用p7zip虽然支持多种格式,但是不容易裁剪,使用lzma SDK是首选: 可以在这里找到各种版本:http://zh.sourceforge.jp/projects/sfnet_sevenzip/releases/ 我下载了4.65版本,这个对文件名编码支持没有9.20的好,中文可能有问题,但是我的需求不需要支持中文文件名,所以足够用了. 解压后先看一下7z这个工程
c语言读取csv文件和c++读取csv文件示例分享

C读取csv文件复制代码代码如下: #include <stdio.h>#include <string.h> char *trim(char *str){ char *p = str; while (*p == ' ' || *p == '\t' || *p == '\r' || *p == '\n') p ++; str = p; p = str + strlen(str) - 1; while (*p == ' ' ||
C语言字符串快速压缩算法代码

通过键盘输入一串小写字母(a~z)组成的字符串. 请编写一个字符串压缩程序,将字符串中连续出席的重复字母进行压缩,并输出压缩后的字符串. 压缩规则: 1.仅压缩连续重复出现的字符.比如字符串"abcbc"由于无连续重复字符,压缩后的字符串还是"abcbc". 2.压缩字段的格式为"字符重复的次数+字符".例如:字符串"xxxyyyyyyz"压缩后就成为"3x6yz". 示例输入:"cccddec
C语言中压缩字符串的简单算法小结

应用中,经常需要将字符串压缩成一个整数,即字符串散列.比如下面这些问题: (1)搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节.请找出最热门的10个检索串. (2)有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M.返回频数最高的100个词. (3)有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复.要求你按照query的频度排序. (4)给定a.b两个文件
Go语言中的字符串拼接方法详情

目录 1.string类型 2.strings包 2.1 strings.Builder类型 2.2 strings.Reader类型 3.bytes.Buffer 3.1 bytes.Buffer:写数据 3.2 bytes.Buffer:读数据 4.字符串拼接 4.1 直接相加 4.2strings.Builder 4.3 strings.Join() 4.4 bytes.Buffer 4.5 append方法 4.6 fmt.Sprintf 5.字符串拼接性能测试 1.string类型 s
详解C语言中的字符串数组

在C语言当中,字符串数组可以使用: char a[] [10]; 或者 char *a[]; 表示第一种表示方式固定了每个字符串的最大大小.第二种没有字符串的大小限制. #include <stdio.h> #include <string.h> //该程序的功能是输入阿拉伯数字的月份数输出英文月份 int main() { //一个字符串数组它的下标代表英文月份的阿拉伯数字 char *month[] = {"January","Februa
C语言中求字符串长度的函数的几种实现方法

1.最常用的方法是创建一个计数器,判断是否遇到'\0',不是'\0'指针就往后加一. int my_strlen(const char *str) { assert(str != NULL); int count = 0; while (*str != '\0') { count++; str++; } return count; } 2.不创建计数器,从前向后遍历一遍,没有遇到'\0'就让指针向后加一,找到最后一个字符,记下来地址,然后用最后一个字符的地址减去起始地址,就得到了字符串的长度.
Go语言中的字符串处理方法示例详解

1 概述字符串,string,一串固定长度的字符连接起来的字符集合.Go语言的字符串是使用UTF-8编码的.UTF-8是Unicode的实现方式之一. Go语言原生支持字符串.使用双引号("")或反引号(``)定义. 双引号:"", 用于单行字符串. 反引号:``,用于定义多行字符串,内部会原样解析. 示例: // 单行 "心有猛虎,细嗅蔷薇" // 多行 ` 大风歌大风起兮云飞扬. 威加海内兮归故乡. 安得猛士兮守四方! ` 字符串支持转义
C语言完整实现12种排序算法(小结)

目录 1.冒泡排序 2.插入排序 3.折半插入排序 4.希尔排序 5.选择排序 6.鸡尾酒排序 7.堆排序 8.快速排序 9.归并排序 10.计数排序 11.桶排序 12.基数排序 1.冒泡排序思路:比较相邻的两个数字,如果前一个数字大,那么就交换两个数字,直到有序.时间复杂度O(n^2),稳定性:这是一种稳定的算法.代码实现: void bubble_sort(int arr[],size_t len){ size_t i,j; for(i=0;i<len;i++){ bool hasSwa
详解C语言中的字符串拼接(堆与栈)

首先来看一个demo: int do_sth(int type) { char *errstr; switch(type) { case 1: errstr = "Error";break case 2: errstr = "Warn";break case 3: errstr = "Info";break case 4: errstr = "Debug";break default: return 0; } if (...)
Go语言中切片使用的注意事项小结

前言 Go 语言中的slice类型可以理解为是数组array类型的描述符,包含了三个因素: 指向底层数组的指针 slice目前使用到的底层数组的元素个数,即长度底层数组的最大长度,即容量因此当我们定义一个切片变量,s := make([]int, 5, 10),即为指向了一个最大长度为10的底层数组,目前切片s使用到的长度为5. 在使用切片的时候,有几个注意事项,下面来一起看看吧. 使用append 先看一个例子: // 创建一个整型切片 // 其长度和容量都是 5 个元素 slice :=
C语言中计算字符串长度与分割字符串的方法

C语言strlen()函数:返回字符串的长度头文件: #include <string.h> strlen()函数用来计算字符串的长度,其原型为: unsigned int strlen (char *s); [参数说明]s为指定的字符串. strlen()用来计算指定的字符串s 的长度,不包括结束字符"\0". [返回值]返回字符串s 的字符数. 注意一下字符数组,例如 char str[100] = "http://see.xidian.edu.cn/cpp
C语言中的字符串数据在C中的存储方式

目录内存中的五大区域字符串数据在C语言中有两种存储方式几个比较容易混的点统计字符串中某一个字符出现的次数使用字符指针数组来存储多个字符串数据内存中的五大区域栈:是专门用来存储局部变量的,所有的局部变量都是声明在栈区域中堆:允许程序员手动的从堆申请指定字节数的空间来使用 BSS段:是用来存储未初始化的全局变量和静态变量,声明一个全局变量,如果我们没有初始化,在程序运行最开始的时候,这个全局变量是没有初始化的,存储在BSS段[程序运行后系统就自动的初始化为0,并把初始化后的全局变量存

C语言中压缩字符串的简单算法小结

相关推荐

随机推荐