单词的记忆方法有什么好方法,英语单词词根记忆法详解,强大的字典树系列01:经典的字典树总结

极简大道 极简大道 2023-10-08 记忆方法 阅读: 143
摘要: 1.简介字典树,即trie树,又称前缀树、单词查找树,可以利用字符串的公共前缀来减少查询时间,因此广泛应用于NLP、搜索、统计等领域。

1.简介

字典树,即trie树,又称前缀树、单词查找树,可以利用字符串的公共前缀来减少查询时间,因此广泛应用于NLP、搜索、统计等领域。

下面简要介绍一些经典的字典树实现,以供大家在使用时参考。

2.总结

Trie

基本原理

特性

Array Trie

每层都有一个大小为V的数组,保存字符集及指向下一状态的指针

查询快,时间复杂度为O(L);体积大,空间复杂度为O(VL);以空间换时间

List Trie

使用可变数组,根据节点的数量动态调整数组的长度

降低了空间浪费,但查询的时间复杂度变为O(nL)

Hash Trie

以hashmap代替可变数组

平衡了数组和可变数组实现的优劣

Double-array Trie

通过base和check两个数组的配合来实现紧凑的存储和高效的查询

体积很小,查询速度接近Array Trie

LOUDS

使用bit编码以减小存储;对树按BFS遍历,每个节点编码为子节点个数*1+0;使用select和rank来支持遍历、查询等操作

体积极小,接近信息论的理论编码下界;但查询速度慢于双数组实现

符号说明:V为字符集大小,L为字符串最大长度,n为平均每层节点数量。

标准字典树(Standard/Array Trie)

链表字典树(List Trie)

双数组字典树(Double Array Trie)

LOUDS

3.参考资料

图片引自参考资料及相关网络内容,侵删~。

这里主要总结了各种字典树的特性,有空会再介绍下实践中各种字典树的性能对比,至于原理,网上已经很多了,包括下面这些优秀的资料,可能就无须我赘述了。

1.小白详解 Trie 树

2.https://zhuanlan.zhihu.com/p/38194127

3.https://zhuanlan.zhihu.com/p/109909494

4.https://www.sohu.com/a/255558996_775361

5.https://zhuanlan.zhihu.com/p/35193582

其他相关
英语音节划分规则口诀,艾宾浩斯单词记忆法,用音标拼读单词,学好r音节的发音规律,音形记忆单词好处多!

英语音节划分规则口诀,艾宾浩斯单词记忆法,用音标拼读单词,学好r音节的发音规律,音形记忆单词好处多!

作者: 极简大道 时间:2023-12-28 阅读: 143
零碎的知识学起来总是力不从心!零碎的知识最怕总结!精炼的总结让人学习高效、简明。有效的总结才是学习正道!敬请关注“语言学科之母“,分享给你精炼的知识,简单高效的方法。打破你的固有传统思维,这就是我要做的。上一节分析了单词音节的分类及怎样划分音节。把音节学好了有两大好处:1)单词音节划分清楚了,你的读音就更准确了。读音准确了,听力就提高了。2)形到音,音到形,反复练习,读听后记单词就是自然本能反应。本能记单词比死记硬背谁高效?...
谐音记忆法的有趣例子,英语音节划分规则口诀,中国人是不是天生记不住英语单词-如何通过音节记单词?

谐音记忆法的有趣例子,英语音节划分规则口诀,中国人是不是天生记不住英语单词-如何通过音节记单词?

作者: 极简大道 时间:2023-12-28 阅读: 135
记单词,是每一个英语学习者必须迈过的一道大坎,无一幸免!词汇量在英语使用中的重要性催生了单词积累漫漫长路上成百上千种五花八门的记忆方法,这其中有好的,也有坏的。好方法可以让我们事半功倍,而坏方法则让很多英语学习者尤其是初学者一开始就误入了歧途。本人在英语学习和使用过程中接触过不少比较有效的方法,以下主要介绍如何通过音节记单词。注意,不是谐音,是音节。相信现在还有很多英语学习者尤其是在校的中小学生还在使用谐音记单词的方法,比如把ambulance(救护车)标成“俺不能死”,把customer(顾客)标成“砍死他们”,把juvenile(青少年)标成“猪喂奶”等等。这种方法虽然比较有趣,也能稍微减轻一下记忆的压力,但从科学和长远的角度来讲是非常不可取的,因为首先并不是每一个英语单词都能这么“被谐音”的,其次这些谐音读法在外国人听起来简直跟火星语无异,不但不利于记住单词的正确读法,反而会不断巩固错误的发音而导致后期越来越难纠正(话说回来,语言学习本应该一开始就要把每一步学好,何须后期再去纠正?可悲啊)。...
月份单词有趣记忆法,快速记忆法,特级英语教师整理:初三全册重点单词、短语、句型和语法考点

月份单词有趣记忆法,快速记忆法,特级英语教师整理:初三全册重点单词、短语、句型和语法考点

作者: 极简大道 时间:2023-12-09 阅读: 142
给大家总结了人教版初三全册所有重难点和必考点,包括重点单词、短语、句型及其用法和语法考点,大家收藏起来好好学吧!...

年度爆文