C# 词典数据结构设计【附demo】

分析

要建立词典,最基本的应该有词典的描述信息、词典索引文件以及词典数据文件。 /// <summary> /// 索引文件 /// </summary> string idxFile = "dic.idx"; /// <summary> /// 数据文件 /// </summary> string dictfile = "dic.dict"; /// <summary> /// 词典信息文件 /// </summary> string ifoFile = "dic.ifo"; 我们建立对应的三个类

详细的代码如下:

/// 
    ///  词语解释
    /// 
    class DictWord
    {
        /// 
        /// 解析
        /// 
        public string Description
        {
            get;
            set;
        }
    }

    /// 
    /// 词典索引
    /// 
    class DictIndex
    {
        /// 
        /// 词语
        /// 
        public string Word
        {
            get;
            set;
        }

        /// 
        /// 偏移
        /// 
        public int Offset
        {
            get;
            set;
        }

        /// 
        /// 数据大小
        /// 
        public int DataSize
        {
            get;
            set;
        }
    }

    /// 
    /// 词典信息
    /// 
    class DictInfo
    {
        /// 
        /// 词典名称
        /// 
        public string BookName
        {
            get;
            set;
        }

        /// 
        /// 收录词数
        /// 
        public int WordCount
        {
            get;
            set;
        }

        /// 
        /// 当前偏移
        /// 
        public int CurrentOffset
        {
            get;
            set;
        }
    }

数据结构说明:

  1. 描述信息包含词典名字,词典词语数量
  2. 索引文件存储的是排好顺序词语的索引,每个索引包含词语名称、存在数据文件中的偏移量、以及数据块大小,排序的目的在于查找时直接用二分查找节省查找时间。
  3. 数据块就简单了,就纯粹的数据

建立词典

建立词典比较简单,首先,定义几个变量来存储词典相关信息:         DictInfo info;         SortedList<string, DictIndex> indexs;         List<DictWord> words;

ps: SortedList能直接排序,不用我们再手动排序了

然后我们来看添加词语:

/// 
        /// 添加词语
        /// 
        ///  
        ///  
        public void Add(string word, string description)
        {
 
            words.Add(new DictWord() { Description = description });
            indexs.Add(word, new DictIndex { DataSize = Encoding.UTF8.GetBytes(description).Length, Offset = info.CurrentOffset, Word = word });
            // 数量++
            info.WordCount++;
            // 偏移++
            info.CurrentOffset += Encoding.UTF8.GetBytes(description).Length;
        }

非常简单,就是添加索引,同时把词典的数量加1

最后来看怎么存储到文件:

/// <summary>
/// 保存
/// </summary>
public void Save()
{
 
    StringBuilder dicBuilder = new StringBuilder();
    dicBuilder.AppendLine(string.Format("BookName={0}", info.BookName));
    dicBuilder.AppendLine(string.Format("WordCount={0}", info.WordCount));
    dicBuilder.AppendLine(string.Format("CurrentOffset={0}", info.CurrentOffset));
    File.WriteAllText(ifoFile, dicBuilder.ToString(), Encoding.UTF8);
 
    dicBuilder = new StringBuilder();
 
    using (BinaryWriter idxWriter = new BinaryWriter(File.Open(dictfile, FileMode.Create)))
    {
        foreach (var word in words)
        {
            idxWriter.Write(Encoding.UTF8.GetBytes(word.Description));
        }
    }
 
    using (BinaryWriter idxWriter = new BinaryWriter(File.Open(idxFile, FileMode.Create)))
    {
        foreach (var index in indexs)
        {
            // 分块大小  128+4+4  = 136
 
            // word 最长128
            byte[] word = new byte[128];
            var wordData = Encoding.UTF8.GetBytes(index.Key);
            var length = Math.Min(128, wordData.Length);
            for (var i = 0; i < length; i++)
            {
                word[i] = wordData[i];
            }
            idxWriter.Write(word);
            byte[] re = new byte[4];
 
            idxWriter.Write(index.Value.Offset);
            idxWriter.Write(index.Value.DataSize);
        }
    }
 
}

这里注意下word最多能存128个字节,每个index区地大小为128+4+4 = 136字节

查询词典

前面做这么多准备,不都是为了查询吗?木有查询,神马都是浮云!

前面说到了,索引文件存储的是排序好的词语列表,所以查询就比较简单了 先给出两个辅助方法:             idxStream = new FileStream(idxFile, FileMode.Open);             idxReader = new BinaryReader(idxStream);             dictStream = new FileStream(dictfile, FileMode.Open);             dictReader = new BinaryReader(dictStream); (1) 获取指定位置的索引

/// 
///  获取指定位置的索引
/// 
///  
/// 
public DictIndex GetWordIndex(int wordIndex)
{
    idxStream.Seek(0, SeekOrigin.Begin);
    idxStream.Seek(wordIndex * 136, SeekOrigin.Begin);
    byte[] word = idxReader.ReadBytes(128);
    var dicIndex = new DictIndex();
    dicIndex.Word = Encoding.UTF8.GetString(word).Replace("\0", "");
    dicIndex.Offset = idxReader.ReadInt32();
    dicIndex.DataSize = idxReader.ReadInt32();
    return dicIndex;
}

(2)获取指定索引对应的词语解释

/// 
///  获取指定词语的解释
/// 
///  
/// 
public string GetWordDescription(DictIndex dictIndex)
{
    dictStream.Seek(0, SeekOrigin.Begin);
    if (dictIndex.Offset != 0)
        dictStream.Seek(dictIndex.Offset, SeekOrigin.Begin);
    byte[] word = dictReader.ReadBytes(dictIndex.DataSize);
    return Encoding.UTF8.GetString(word).Replace("\0", "");
}

现在开始二分查找:

/// 
        /// 获取词语解释
        /// 
        ///  
        /// 
        public string GetDescription(string word)
        {
            var i = 0;
            var mid = info.WordCount / 2;
            var max = info.WordCount;
            DictIndex w = new DictIndex();
            while (i <= max)
            {
                mid = (i + max) / 2;
                w = GetWordIndex(mid);
                if (string.Compare(w.Word, word) > 0)
                {
                    max = mid - 1;
                }
                else if (string.Compare(w.Word, word) < 0)
                {
                    i = mid + 1;
                }
                else
                {
                    break;
                }
            }
 
            return "[" + w.Word + "]\n" + GetWordDescription(w);
        }

此部分完整代码:

/// 
    /// 词典
    /// 
    class Dict
    {
        DictInfo info;
        SortedList indexs;
        List words;

        /// 
        /// 索引文件
        /// 
        string idxFile = "dic.idx";

        /// 
        /// 数据文件
        /// 
        string dictfile = "dic.dict";

        /// 
        /// 词典信息文件
        /// 
        string ifoFile = "dic.ifo";

        BinaryReader idxReader;
        FileStream idxStream;
        BinaryReader dictReader;
        FileStream dictStream;


        /// 
        /// 查询使用
        /// 
        public Dict()
        {
            LoadDictInfo();
            idxStream = new FileStream(idxFile, FileMode.Open);
            idxReader = new BinaryReader(idxStream);
            dictStream = new FileStream(dictfile, FileMode.Open);
            dictReader = new BinaryReader(dictStream);
        }

        /// 
        /// 创建时使用
        /// 
        ///  
        public Dict(string name)
        {
            info = new DictInfo { BookName = name, WordCount = 0, CurrentOffset = 0 };
            indexs = new SortedList();
            words = new List();

        }

        /// 
        /// 获取词语解释
        /// 
        ///  
        /// 
        public string GetDescription(string word)
        {
            var i = 0;
            var mid = info.WordCount / 2;
            var max = info.WordCount;
            DictIndex w = new DictIndex();
            while (i <= max)
            {
                mid = (i + max) / 2;
                w = GetWordIndex(mid);
                if (string.Compare(w.Word, word) > 0)
                {
                    max = mid - 1;
                }
                else if (string.Compare(w.Word, word) < 0)
                {
                    i = mid + 1;
                }
                else
                {
                    break;
                }
            }

            return "[" + w.Word + "]\n" + GetWordDescription(w);
        }



        /// 
        ///  获取指定位置的索引
        /// 
        ///  
        /// 
        public DictIndex GetWordIndex(int wordIndex)
        {
            idxStream.Seek(0, SeekOrigin.Begin);
            idxStream.Seek(wordIndex * 136, SeekOrigin.Begin);
            byte[] word = idxReader.ReadBytes(128);
            var dicIndex = new DictIndex();
            dicIndex.Word = Encoding.UTF8.GetString(word).Replace("\0", "");
            dicIndex.Offset = idxReader.ReadInt32();
            dicIndex.DataSize = idxReader.ReadInt32();
            return dicIndex;
        }

        /// 
        ///  获取指定词语的解释
        /// 
        ///  
        /// 
        public string GetWordDescription(DictIndex dictIndex)
        {
            dictStream.Seek(0, SeekOrigin.Begin);
            if (dictIndex.Offset != 0)
                dictStream.Seek(dictIndex.Offset, SeekOrigin.Begin);
            byte[] word = dictReader.ReadBytes(dictIndex.DataSize);
            return Encoding.UTF8.GetString(word).Replace("\0", "");
        }

        /// 
        /// 添加词语
        /// 
        ///  
        ///  
        public void Add(string word, string description)
        {

            words.Add(new DictWord() { Description = description });
            indexs.Add(word, new DictIndex { DataSize = Encoding.UTF8.GetBytes(description).Length, Offset = info.CurrentOffset, Word = word });
            // 数量++
            info.WordCount++;
            // 偏移++
            info.CurrentOffset += Encoding.UTF8.GetBytes(description).Length;
        }

        /// 
        /// 加载词典信息
        /// 
        void LoadDictInfo()
        {
            var infos = File.ReadAllLines(ifoFile);
            info = new DictInfo
            {
                BookName = infos[0].Replace("BookName=", "").Trim(),
                WordCount = int.Parse(infos[1].Replace("WordCount=", "").Trim()),
                CurrentOffset = int.Parse(infos[2].Replace("CurrentOffset=", "").Trim()),
            };
        }

        /// 
        /// 保存
        /// 
        public void Save()
        {

            StringBuilder dicBuilder = new StringBuilder();
            dicBuilder.AppendLine(string.Format("BookName={0}", info.BookName));
            dicBuilder.AppendLine(string.Format("WordCount={0}", info.WordCount));
            dicBuilder.AppendLine(string.Format("CurrentOffset={0}", info.CurrentOffset));
            File.WriteAllText(ifoFile, dicBuilder.ToString(), Encoding.UTF8);

            dicBuilder = new StringBuilder();

            using (BinaryWriter idxWriter = new BinaryWriter(File.Open(dictfile, FileMode.Create)))
            {
                foreach (var word in words)
                {
                    idxWriter.Write(Encoding.UTF8.GetBytes(word.Description));
                }
            }

            using (BinaryWriter idxWriter = new BinaryWriter(File.Open(idxFile, FileMode.Create)))
            {
                foreach (var index in indexs)
                {
                    // 分块大小  128+4+4  = 136

                    // word 最长128
                    byte[] word = new byte[128];
                    var wordData = Encoding.UTF8.GetBytes(index.Key);
                    var length = Math.Min(128, wordData.Length);
                    for (var i = 0; i < length; i++)
                    {
                        word[i] = wordData[i];
                    }
                    idxWriter.Write(word);
                    byte[] re = new byte[4];

                    idxWriter.Write(index.Value.Offset);
                    idxWriter.Write(index.Value.DataSize);
                }
            }

        }
    }

演示

如图所示

文件夹中放置了许多文本文件,内容为词语的解释

首先、建立词典:

Dict dic = new Dict("病症词典");
  
            var files = new DirectoryInfo(@"G:\Users\Administrator\Desktop\新建文件夹 (3)\新建文件夹 (3)").GetFiles();
            foreach (var file in files)
            {
                Console.WriteLine(file.FullName);
                dic.Add(file.Name.Replace("的症状.txt", ""), File.ReadAllText(file.FullName));
            }
            dic.Save();

然后、把玩一番:

var dict = new Dict();
            while (true)
            {
                Console.Write("请输入词语:");
                var w = Console.ReadLine();
                Stopwatch sw = new Stopwatch();
                sw.Start();
                Console.WriteLine("找到词语:");
                Console.WriteLine(dict.GetDescription(w));
                sw.Stop();
                Console.WriteLine("耗时:" + sw.ElapsedMilliseconds + "ms");

            }

运行结果:

到此为止,谢谢收看!

[[demo下载]]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏me的随笔

使用AutoMapper进行对象间映射

在开发过程中,难免遇到下面这种情况:两个(或多个)对象所拥有的大多数属性是重复的,我们需要在对象间进行映射(即将一个对象的属性值赋给另一个对象。通常我们可以进行...

5342
来自专栏跟着阿笨一起玩NET

[整理]如何做一个语法着色控件

很多IDE或者开发工具中都有语法着色的功能,这是如何实现的呢?笔者试着用C#做了一个Sample,基本上实现此功能。

722
来自专栏木宛城主

浪客剑心:位图法Bitmap算法分析

看了一篇文章《一道腾讯前端试题,谁来试试身手》,正好以前了解过位图法,确实不错。位图法适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不...

3646
来自专栏salesforce零基础学习

salesforce 零基础学习(三十九) soql函数以及常量

在salesforce中,我们做SOQL查询时,往往需要用到计算式,比如求和,求平均值,或者过滤数据时,往往需要通过时间日期过滤,SOQL已经封装了很多的函数,...

6060
来自专栏青玉伏案

Oracle常用函数

前一段时间学习Oracle 时做的学习笔记,整理了一下,下面是分享的Oracle常用函数的部分笔记,以后还会分享其他部分的笔记,请大家批评指正。 1.Oracl...

2119
来自专栏积累沉淀

Hadoop学习之网络爬虫+分词+倒排索引实现搜索引擎案例

本项目实现的是:自己写一个网络爬虫,对搜狐(或者csdn)爬取新闻(博客)标题,然后把这些新闻标题和它的链接地址上传到hdfs多个文件上,一个文件对应一个标题和...

2527
来自专栏跟着阿笨一起玩NET

.NET常用操作小知识

 var v = StringTruncat("广东省深圳市西乡镇宝安区", 10, "...");

611
来自专栏Java成神之路

HQL语句大全

Hibernate配备了一种非常强大的查询语言,这种语言看上去很像SQL。但是不要被语法结构 上的相似所迷惑,HQL是非常有意识的被设计为完全面向对象的查询,它...

1775
来自专栏MasiMaro 的技术博文

OLEDB 静态绑定和数据转化接口

OLEDB 提供了静态绑定和动态绑定两种方式,相比动态绑定来说,静态绑定在使用上更加简单,而在灵活性上不如动态绑定,动态绑定在前面已经介绍过了,本文主要介绍OL...

1131
来自专栏大内老A

Enterprise Library深入解析与灵活应用(9):个人觉得比较严重的关于CachingCallHandler的Bug

微软EnterLib的Policy Injection Application Block(PIAB)是一个比较好用的轻量级的AOP框架,你可以通过创建自定义的...

2089

扫码关注云+社区

领取腾讯云代金券