# poc-dict

**Repository Path**: luccas/poc-dict

## Basic Information

- **Project Name**: poc-dict
- **Description**: 大二上《数据结构与算法》课设
迷你英汉电子词典 PocDIct
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2021-12-03
- **Last Updated**: 2022-12-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# PocDict

## 介绍

大二数据结构课设 - 迷你英汉电子词典 PocDIct

## 技术栈

编程语言：Java

版本管理：Git

IDE：Idea

## RELEASE1.0

### 数据结构（开散列表）：

1. Record：单词及其翻译

2. SortedLinkedList：有序（字典序）双向链表，数据域为Record，满足基本CURD

3. Dictionary：字典，由开散列Hash表组成，满足基本CRUD

    1. Hash数组大小26，对应26个字母
    2. 数组存储对应SortedLinkedList；

4. ~~布隆过滤器（否决）~~

   否决原因：不支持删除

   > 使用布隆过滤器的初衷在于过滤单词访问，当遇到过滤器中不存在的单词不进行查询，直接驳回请求。
   >
   > 这也是布隆过滤器的主要适用场景之一，隔离数据源和请求（无效请求隔离）。
   >
   > 伴随着亿级数据过滤能力和空间占用少的强大优点的，是其存在误判和无法支持数据源进行数据删除的缺点。
   >
   > - 误判：由于生成hash是一种信息压缩算法，存在的hash冲突符合信息学中压缩导致的失真现象，所以对于存在hash冲突的结果会出现相同的判断，也就是误判。
   >
   > - 无法支持数据删除：与误判类似，由于过滤器中的结果是多方数据压缩后得到的结果，同样的结果可能来自不同的记录，如果删除数据的同时，删除其对应的hash，会导致与其存在hash冲突的记录全部被视为"删除"，造成更严重的“误判”。

<br>

### 工具类：

1. Wordloader：单词加载类，配合多线程、文件IO实现字典数据初始化。

<br>

### 页面：

1. TranslationGui：翻译界面
2. CreateRecordGui：新增记录界面
3. DeleteRecordGui：删除记录界面

<br>

## RELEASE2.0

### 数据结构

#### 核心数据结构升级为前缀树

- TrieNode：前缀树节点
  1. 使用数组存放当前前缀的下一位前缀索引
  1. 如果从头到当前位是一个单词，则存储其翻译

- Dictonary：字典
  1. 维护一个前缀树的根节点，支持基本CRUD



**优点**：

1. 减少了相同前缀单词的存储浪费
2. 支持动态查询（数据结构层面）
3. 不存在hash冲突，解决了hash表因大量hash冲突带来的性能下降



**缺点**：

1. 可能出现一个单词单独占用了一条分支，形成单支树，相比直接存，占用更多内存。
2. 增加和删除时的逻辑处理更麻烦，耗时更久
3. 采用数组存放后缀，因此只支持ASCII码大于等于0的字符存储，形如`'-'、'\'、'.'`存储不便

<br>

### 工具类

#### Wordloader：为支持新的数据结构做了一些优化



<br>


## RELEASE3.0

### 更新：

1. 核心数据结构升级为AVL树（一种平衡二叉查找树）