存档

文章标签 ‘trie树’

查找字典中某个公共前缀的所有单词

2013年3月14日 2 条评论

---

练手,求给定公共前缀的所有单词集合,使用trie树,找到公共前缀后,DFS深搜即可。在Trie树节点中增加一个记录以当前串为前缀的单词个数,可以直接返回公共前缀单词个数。在Trie树类中增加一个存储公共前缀单词的集合指针,存储所求单词集合。

阅读全文...

兄弟单词 — 两种算法实现

2013年2月28日 2 条评论

---

兄弟单词这个题目最初见于《编程珠玑》,但是里面给出的方法是最笨的,一般不提倡采用吧;这个题目在之前的百度面试中也遇到过,本文实现两种方法的代码,方法如下:

方案一:使用数据结构 map<key,list>。兄弟单词共用一个签名key,key为单词内部排序后的词条,list存储同一key的单词集合;相对于编程珠玑中的方法,该方法在空间上节省了每个单词一个key的空间;在时间上,不再需要二分查找,O(1)的查找;但是这种方法还可以优化,见方案二

方案二:使用trie树。trie树又称字典树,在面试题中关于“字符串”与“数字串”类型的问题中高频出现,非常实用。对于兄弟单词,兄弟单词公用一个key自不必说,只是trie的节点结构应该多出一个域list,用来存储key对应的兄弟单词;具体节点结构应该为


bool isStr, Node* next[26], vector<const char*> brothers

该方案查询的复杂度为O(L),L为key的平均长度;空间上则有很大的优化,例如单词的key有“abc”、“abcd”、“abcde”之类的形式,则这些key也能达到空间公用,不过数据量大还好,数据量小,trie树开辟的空间还是有些浪费的,不多言,上代码:

【测试用例】


input:

cba acb bc cb b

output:

cba acb

bc cb

b

【方案一:使用哈希map实现兄弟单词】

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define MAXLEN 100  /* 单词最大长度 */

/* qsort比较函数 */
int charcmp(const void *p, const void *q)
{
	return *(char *)p - *(char *)q;
}

/* 打印输出 & 释放内存 */
void output(map<string,vector<char*>> dic)
{
	for(map<string,vector<char*>>::iterator it = dic.begin(); it != dic.end(); ++it)
	{
		for(vector<char *>::iterator itv = it->second.begin(); itv != it->second.end(); ++itv)
		{
			printf("%s ",*itv);
			free(*itv);
		}
		printf("\n");
	}
}

void main()
{
	map<string,vector<char*>> dic;  /* 存储<key,兄弟单词集> */
	char word[MAXLEN];
	int len = 0;

	while(scanf("%s",word) != EOF) /* ctrl+z结束输入 */
	{
		len = strlen(word);
		if(len > 0)
		{
			char * ptr = (char *) malloc(len+1);
			strcpy(ptr,word);
			qsort(word,len,sizeof(char),charcmp);
			string key(word);
			dic[key].push_back(ptr);
		}
	}
	output(dic);
}

【方案二:使用trie树实现兄弟单词】

阅读全文...

字符串排序新探索——使用基数排序

2012年7月7日 1 条评论

---

一个偶然的机会发现字符串排序也可以使用基数排序来实现,而且是一个很有意思的问题,因为这其中有一个渐进优化的过程,本文先考虑字符串排序的几种实现方法,然后从理论上分析使用基数排序的复杂度,最后将其与快排进行定性比较,从理论和实现两方面验证在字符串排序问题中,基数排序何时超越快排。

那么字符串排序有哪些方法呢?这里给出一个简洁列表,欢迎补充

  1. 快速排序:最简单最直接的方法,但是规模稍大,字符串大量移动和复制的开销会特别大。
  2. 先做地址索引,然后快排:目前来讲,这似乎应该是最优的方法,有效避免了字符串的移动和复制开销,时间复杂度为O(Lcmp*N*lgN)。Lcmp是字符串比较时的平均比较长度,这个我们稍后做定量计算。
  3. Trie树:这是我写本文草稿时忽然想到的,这种方法也不错,如果串有重复可以在节点设置一个计数域;优点是能有效节省空间,大规模字符串真能节省不少空间呢,内存有限情况下可以考虑,而且理论上复杂度是线性的O(Lave*N),Lave为字符串平均长度,N为串个数;缺点是什么呢?缺点是建树过程要不断的申请开辟空间,大规模情况下这个开销不可忽视;不过我觉得仍然可以一试,改天我再做一个测试,看看百万级规模情况下(硬件条件有限,千万级就做不来了)时间与快排比起来怎么样,本节稍后我们可以从理论上做一个大致的分析。
  4. 基数排序:以上三种方法应该说比较容易想到,也比较常规;偶然发现基数排序在这方面也是有用武之地的,而且某些情况下,它的性能是超越第二种快排方法的,同时在实现上,我们也可以将基数排序分配和收集过程中空间的申请和释放优化掉,甚至可以通过数据结构的有效设计来优化掉桶元素的添加和删除操作时的开销。基数排序的复杂度为O(Lmax*N),Lmax是待排字符串的最大长度,这也是限制基数排序的地方。
  5. Summary:个人认为在实际应用时,后三种方法都是可以考虑的,优先考虑索引快排和Trie树,在了解本文之后,可以知道某些特定情况下基数排序也是不错的选择。

下面说一下,基数排序字符串实现中的几个问题,几个关键词:

阅读全文...

trie树--详解

2011年8月31日 9 条评论

    前几天学习了并查集和trie树,这里总结一下trie。

    本文讨论一棵最简单的trie树,基于英文26个字母组成的字符串,讨论插入字符串、判断前缀是否存在、查找字符串等基本操作;至于trie树的删除单个节点实在是少见,故在此不做详解。

  • Trie原理

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

  • Trie性质

好多人说trie的根节点不包含任何字符信息,我所习惯的trie根节点却是包含信息的,而且认为这样也方便,下面说一下它的性质 (基于本文所讨论的简单trie树)

1.    字符的种数决定每个节点的出度,即branch数组(空间换时间思想)

2.    branch数组的下标代表字符相对于a的相对位置

3.    采用标记的方法确定是否为字符串。

4.    插入、查找的复杂度均为O(len),len为字符串长度

  • Trie的示意图

如图所示,该trie树存有abc、d、da、dda四个字符串,如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL

阅读全文...