huggingface之tokenization基础结构Trie-代码解读

目的

基于transformers查看字典树是怎么生成的呢,输入字符串text是怎么在字典树中进行分割的,一起来看一下

参考链接

wikipedia

代码

def traversal_states_second(states, offsets, start, current, text, skip, reset, to_remove):# trie_pointer存在最后终止符,需要重置和存储结果在offsets中# lookahead要匹配最长的# 比如extra_id_1 vs extra_id_100这种,先找到extra_id_1,还是会继续匹配的# "[CLS]", "L" 匹配CLSfor lookstart, looktrie_pointer in states.items():# if lookstart in to_remove:# 额外处理一下的,处理那个bug#      continueif lookstart > start:# This partial match is later, we can stop lookingbreak# 这个匹配是后面的结果,可以停止看了"""trie = Trie()trie.add("喜欢你")trie.add("欢你")trie.split("我喜欢你一起玩")# ['我', '喜欢你', '一起玩']# 当匹配到char“一”的时候,states=OrderedDict([(1, {'': 1}), (2, {'': 1})])# start=1时,trie_pointer = {'': 1} 则'' in trie_pointer为true# 开始重新遍历states# lookstart=2时,lookstart>start,这里对应的token "欢你" 已经是后面的匹配了,停止"""elif lookstart < start:# This partial match is earlier, the trie pointer# was already updated, so index is + 1# 这是前面的匹配,trie_pointer已经更新了,所以index=当前+1lookahead_index = current + 1end = current + 1"""trie = Trie()trie.add("喜欢你")trie.add("欢")trie.split("我喜欢你一起玩")# ['我', '喜欢你', '一起玩']# 当匹配到char“你”的时候,states=OrderedDict([(1, {'你': {'': 1}}), (2, {'': 1})])# start=2时,trie_pointer = {'': 1} 则'' in trie_pointer为true# 开始重新遍历states# lookstart=1时,lookstart<start# 虽然是在"欢"时找到了对应的终止符,但是前面的匹配"喜欢"也不能不管了,所以要看一下下面的char是否匹配"""else:# Here lookstart == start and#      looktrie_pointer == trie_pointer# It wasn't updated yet so indices are current oneslookahead_index = current# 当前token对应的位置end = current# """trie = Trie()trie.add("喜欢你")trie.split("我喜欢你一起玩")# ['我', '喜欢你', '一起玩']# 当匹配到char“一”的时候,states=OrderedDict([(1, {'': 1})])# start=1时,trie_pointer = {'': 1} 则'' in trie_pointer为true# 开始重新遍历states# lookstart=1时,lookstart=start# 当前token并未验证是否在trie_pointer中,所以需要记录当前char对应的位置"""next_char = text[lookahead_index] if lookahead_index < len(text) else None# 下一个字符,避免extra_id_1 vs extra_id_100这种情况if "" in looktrie_pointer:# 找到终止符了,对应了lookstart == start这种情况start = lookstartend = lookahead_indexskip = lookahead_indexwhile next_char in looktrie_pointer:# 对应lookstart<start这种情况,要把后面的token相同的都找到# 这里start、end值都是有了,可能不更新,也可能更新多轮# 这里我没仔细找例子,先把整个流程跑通,重新找demolooktrie_pointer = looktrie_pointer[next_char]lookahead_index += 1# 后面的char位置if "" in looktrie_pointer:# 找到终止符了start = lookstartend = lookahead_indexskip = lookahead_indexif lookahead_index == len(text):# 我咋没把这种情况测试出来呢# End of stringprint ('End of string')breaknext_char = text[lookahead_index]# End lookahead# Storing and resettingoffsets.append(start)offsets.append(end)reset = Truereturn offsets, skip, reset, to_removedef traversal_states(states, current_char, offsets, current, text, skip, reset, to_remove):for start, trie_pointer in states.items():# 遍历statesif "" in trie_pointer:# 这个指针到结束位置了offsets, skip, reset, to_remove = traversal_states_second(states, offsets, start, current, text, skip, reset, to_remove)breakelif current_char in trie_pointer:# 当前字符在trie_pointer中,则更新指针,将states更新trie_pointer = trie_pointer[current_char]# 喜 欢 和 你states[start] = trie_pointer# 慢慢的找到这个单词的剩余字符else:# 当前字符不能匹配到trie_pointer,需要停止追踪这个匹配# 因为python迭代器的工作方式,不能直接在这个循环中执行这个操作to_remove.add(start)# 因为这里的原因,所以会造成['ab c', 'd']的情况return offsets, skip, reset, to_removeimport bisect
import itertools
import re
import unicodedata
from collections import OrderedDict
from typing import Any, Dict, List, Optional, Tuple, Union, overloadclass Trie:"""Trie in Python. Creates a Trie out of a list of words. The trie is used to split on `added_tokens` in one passLoose reference https://en.wikipedia.org/wiki/Trie"""def __init__(self, *args):self.data = {}self._tokens = set()self._termination_char = ""self.update(*args)def update(self, *args):"""Updates the Trie with new tokens provided as arguments.新单词作为参数更新Triedemo:trie = Trie(("hello","you"))trie.data# {'h': {'e': {'l': {'l': {'o': {'': 1}}}}}, 'y': {'o': {'u': {'': 1}}}}trie._tokens# {'hello', 'you'}Args:*args: Variable number of words to be added to the Trie.添加到Trie的单词"""for token in tuple(*args):self.add(token)def add(self, word: str):"""Passes over every char (utf-8 char) on word and recursively adds it to the internal `data` trie representation.The special key `""` in `self._termination_char` is used to represent termination.This function is idempotent, adding twice the same word will leave the trie unchangedExample:```python>>> trie = Trie()>>> trie.add("Hello 友達")>>> trie.data{"H": {"e": {"l": {"l": {"o": {" ": {"友": {"達": {"": 1}}}}}}}}}>>> trie.add("Hello")>>> trie.data{"H": {"e": {"l": {"l": {"o": {"": 1, " ": {"友": {"達": {"": 1}}}}}}}}}```"""if not word:# ''或者为None# Prevent empty stringreturnself._tokens.add(word)# 要把word添加到self._tokens中ref = self.datafor char in word:ref[char] = ref.setdefault(char, {})# 这一步会更新self.dataref = ref[char]# 这一步不会更新self.dataref[self._termination_char] = 1def split(self, text: str) -> List[str]:"""Will look for the words added to the trie within `text`. Output is the original string splitted along theboundaries of the words found.This trie will match the longest possible word first !Example:```python>>> trie = Trie()>>> trie.split("[CLS] This is a extra_id_100")["[CLS] This is a extra_id_100"]>>> trie.add("[CLS]")>>> trie.add("extra_id_1")>>> trie.add("extra_id_100")>>> trie.split("[CLS] This is a extra_id_100")["[CLS]", " This is a ", "extra_id_100"]```"""# indexes are counted left of the chars index.# "hello", index 0, is left of h, index 1 is between h and e.# index 5 is right of the "o".# States are going to capture every possible start (indexes as above)# as keys, and have as values, a pointer to the position in the trie# where we're at. This is a partial match for now.# This enables to keep track of multiple matches while we're iterating# the string# If the trie contains, "blowing", and "lower" and we encounter the# string "blower", we need to split into ["b", "lower"].# This is where we need to keep track of multiple possible starts.# indexes是字符index的左计数states = OrderedDict()# offsets包含了每一个需要分割的分块,强制在位置0和位置len(text)进行分割offsets = [0]# This is used by the lookahead which needs to skip over# some text where the full match exceeded the place in the initial# for loop# 这是由lookahead使用的,它需要跳过一些完全匹配超出初始 for 循环中位置的文本skip = 0# Main loop, Giving this algorithm O(n) complexity# 主循环,O(n) 复杂的# current是当前位置,current_char是当前字符for current, current_char in enumerate(text):if skip and current < skip:continueto_remove = set()# 将停止匹配的状态,都放到to_remove,停止追踪reset = False# 当找到一个匹配,就丢掉一切,这是一个贪心算法,会匹配到第一个发现的tokenoffsets, skip,reset, to_remove = traversal_states(states, current_char, offsets, current, text, skip, reset, to_remove)# 遍历states,这一步会遍历每个statesif reset:# 找到匹配时,就丢掉一切,即重置statesstates = {}else:# 没有找到匹配,将停止匹配的状态从states中删除,停止追踪for start in to_remove:del states[start]# If this character is a starting character within the trie# start keeping track of this partial match.# 当前字符在self.data中,要开始追踪了# skip代表了最后一个找到的char对应的位置,因为在off_1中也会遍历char位置,所以设置了这样一个位置指针# 贪心算法,前面token已经把这个char使用上了,后面即使有一样的,也不会管了"""trie = Trie()trie.add("喜欢你一")trie.add("一起玩")trie.split("我喜欢你一起玩")# ['我', '喜欢你一', '起玩']"""# self.data = {'喜': {'欢': {'和': {'你': {'': 1}}}, '爱': {'': 1}}, '欢': {'喜': {'': 1}}}# '喜' in self.data == Trueif current >= skip and current_char in self.data:states[current] = self.data[current_char]# 根据current_char在self.data中找到对应的value,即剩余的字符串        # We have a cut at the end with states.for start, trie_pointer in states.items():if "" in trie_pointer:# This is a final match, we need to reset and# store the results in `offsets`.# 最后的匹配了,将结果保存在offsets中end = len(text)offsets.append(start)offsets.append(end)# Longest cut is always the one with lower start so the first# item so we need to break.break# 这里没有看懂return self.cut_text(text, offsets)def cut_text(self, text, offsets):# We have all the offsets now, we just need to do the actual splitting.# We need to eventually add the first part of the string and the eventual# last part.offsets.append(len(text))# 把最开始和最后的部分都要加上tokens = []start = 0for end in offsets:if start > end:print ("There was a bug in Trie algorithm in tokenization. Attempting to recover. Please report it"" anyway.")continueelif start == end:# This might happen if there's a match at index 0# we're also preventing zero-width cuts in case of two# consecutive matchescontinuetokens.append(text[start:end])start = endreturn tokens

测试用例

新建

trie = Trie(("sea","see"))
trie._tokens# {'sea', 'see'}
trie.data# {'s': {'e': {'a': {'': 1}, 'e': {'': 1}}}}
# ->s->e->a
# ->s->e->e

添加

trie = Trie()
trie.add("Hello 友達")
trie.data

分割

trie = Trie()
trie.split("[CLS] This is a extra_id_100")
# ["[CLS] This is a extra_id_100"]trie = Trie()
trie.add("喜欢你")
trie.split("我喜欢你一起玩")trie = Trie()
trie.add("喜欢你一")
trie.add("一起玩")
trie.add("你一起玩")
trie.split("我喜欢你一起玩")
# ['我', '喜欢你一', '起玩']trie = Trie()
trie.add("abc")
trie.add("b")
trie.split("ab cd")
# ['ab c', 'd']
# 这里有个bug,对应了traversal_states_second中的这里# if lookstart in to_remove:# 额外处理一下的,处理那个bug#      continue

额外说几句

查看这个代码的过程中,发现了一个bug,在git上提交了,还没有得到回复,可能是我自己想错了。
这里的代码逻辑比较散,需要对应多种特殊情况,希望能画出流程图来。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/2919.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

鸢尾博客项目开源

1.博客介绍 鸢尾博客是一个基于Spring BootVue3 TypeScript ViteJavaFx的客户端和服务器端的博客系统。项目采用前端与后端分离&#xff0c;支持移动端自适应&#xff0c;配有完备的前台和后台管理功能。后端使用Sa-Token进行权限管理,支持动态菜单权限&#xff0c;服务健康…

IBinder源码分析

基础概念 binder 是 Android 中主要的跨进程通信方式&#xff0c;binder 驱动和 service manager 分别相当于网络协议中的路由器和 DNS&#xff0c;并基于 mmap 实现了 IPC 传输数据时只需一次拷贝。binder 包括 BinderProxy、BpBinder 等各种 Binder 实体&#xff0c;以及对 …

PDF Reader Pro for mac激活版 PDF编辑阅读器

PDF Reader Pro阅读器是一款用户必备的集管理、编辑、转换、阅读功能于一体的专业的全能PDF阅读专家。快速、易用、强大&#xff0c;让您出色完成 PDF 工作&#xff0c;深受全球9000万用户的喜爱。用户可轻松使用PDF Reader Pro进行文档阅读、编辑、注释、填写Form表单、转换、…

图像分割从基础到进阶:阈值化、K-means和Mean-Shift算法的应用

图像分割是计算机视觉中的一项关键技术&#xff0c;用来将图像划分为若干个 有意义 的区域&#xff0c;以便后续的图像处理和分析工作。根据任务的不同&#xff0c;图像分割可以进一步细分为语义分割、实例分割和全景分割&#xff1a; 语义分割 (Semantic Segmentation) 对图像…

生产消费者模型

线程同步 互斥锁(互斥量)条件变量生产/消费者模型 一、互斥锁 C11提供了四种互斥锁&#xff1a; mutex&#xff1a;互斥锁。timed_mutex&#xff1a;带超时机制的互斥锁。recursive_mutex&#xff1a;递归互斥锁。recursive_timed_mutex&#xff1a;带超时机制的递归互斥锁…

国标GB28181视频平台EasyCVR私有化视频平台工地防盗视频监控系统方案

一、方案背景 在当代建筑施工领域&#xff0c;安全监管和防盗监控是保障工程顺利进行和资产安全的关键措施。随着科技进步&#xff0c;传统的监控系统已不足以应对现代工地的安全挑战。因此&#xff0c;基于国标GB28181视频平台EasyCVR的工地防盗视频监控系统应运而生&#xf…

WindowsDocker安装到D盘,C盘太占用空间了。

Windows安装 Docker Desktop的时候,默认位置是安装在C盘,使用Docker下载的镜像文件也是保存在C盘,如果对Docker使用评率比较高的小伙伴,可能C盘空间,会被耗尽,有没有一种办法可以将Docker安装到其它磁盘,同时Docker的数据文件也保存在其他磁盘呢? 答案是有的,我们可以…

【AI日记】24.11.01 LangChain、openai api和github copilot

【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】 工作 工作1 内容&#xff1a;学习deeplearning.ai的免费课程地址&#xff1a;LangChain Chat with Your DataB站地址&#xff1a;https://www.bilibili.com/video/BV148411D7d2github代码&#xff1a;https:…

HTML静态网页成品作业(HTML+CSS)——花主题介绍网页设计制作(1个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有1个页面。 二、作品演示 三、代…

WinCC V7.5 SP1VBS全局变量的使用

1 <概述> 在 WinCC 使用过程中&#xff0c;有很多应用场合需要把获得的数据保存下来&#xff0c;在其它事件 中来使用&#xff0c;例如在 WinCC 运行后去读取自定义的配置文件中的参数&#xff0c;在控制相应设 备时需要根据这些参数来确定控制方式&#xff0c;那么就需…

Charles抓包_Android

1.下载地址 2.破解方法 3.安卓调试办法 查看官方文档&#xff0c;Android N之后抓包要声明App可用User目录下的CA证书 3.1.在Proxy下进行以下设置&#xff08;路径Proxy->Proxy Settings&#xff09; 3.1.1.不抓包Windows&#xff0c;即不勾选此项&#xff0c;免得打输出不…

微信小程序 高校教材征订系统

文章目录 项目介绍具体实现截图技术介绍mvc设计模式小程序框架以及目录结构介绍错误处理和异常处理java类核心代码部分展示详细视频演示源码获取 项目介绍 系统分为三个角色&#xff0c;分别是教材科、系教学秘书、教研室主任。系统主要完成功能是教材科要发布教材征订信息&am…

Rust 力扣 - 1343. 大小为 K 且平均值大于等于阈值的子数组数目

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 长度为k且平均值大于等于阈值的子数组数目 等于 长度为k且总和大于等于k * 阈值的子数组数目 我们遍历长度为k的窗口&#xff0c;我们只需要记录窗口内的总和即可&#xff0c;遍历过程中记录总和大于等于k * 阈…

3DMax使用 MCG实现简单克隆修改器

3DMax中的MCG工具集允许用户创建几种不同类型的插件。在这个例子中&#xff0c;我们正在创建一个简单的克隆修改器。 将修改器添加到对象时&#xff0c;将使用“数量”整数值克隆网格n次&#xff0c;并使用X、Y和Z中的“缩放”、“旋转”和“移动”微调器控制每个网格的偏移。…

收卷锥度张力控制(Simulink建模)

1、收卷锥度张力控制功能块(支持5种锥度曲线) 收卷锥度张力控制功能块(支持5种锥度曲线)-CSDN博客文章浏览阅读340次。1、锥度张力控制张力锥度控制(收卷应用)-CSDN博客文章浏览阅读2.2k次。收卷、放卷应用系列文章可以参看下面的文章链接:变频器简单张力控制(线缆收放卷…

【星闪EBM-H63开发板】小熊派固件中心的使用

目录 引言 固件中心 定制固件 创建配置 透传固件的配置信息 串口配置 SLE无线射频配置 SLE连接配置 硬件配置 生成固件 下载和烧录 结语 引言 前面几天介绍了星闪EBM-H63开发板的情况&#xff0c;今天来试试固件中心。 固件中心 固件中心是小熊派提供的用于生成固…

从《Mixtral of Experts》开始讲讲MoE

MoE 在讲这篇论文前先来说说什么是MoE MoE是什么&#xff1f; MoE&#xff0c;全称Mixture of Experts&#xff0c;混合专家模型。MoE是大模型架构的一种&#xff0c;其核心工作设计思路是“术业有专攻”&#xff0c;即将任务分门别类&#xff0c;然后分给多个“专家”进行解…

Java打造智能语音陪聊软件?提升用户体验的新路径

在现在的日常生活中&#xff0c;大家做什么都会寻找一个“搭子”&#xff0c;例如“游戏搭子”&#xff0c;很多时候一时半会找不到就会很苦恼&#xff0c;就因此诞生了语音陪聊软件。然而Java作为一种广泛使用的编程语言&#xff0c;在开发高效、稳定的应用程序方面具有显著优…

js.轮转数组和旋转链表

这是两个相似的题型&#xff0c;一个是数组&#xff0c;另一个是链表。 链接&#xff1a;189. 轮转数组 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 示例 1:…

004-Kotlin界面开发快速入水之TicTacToe

程序界面和效果 快速入水 要学习一样跟程序设计有关的东西&#xff0c;最好的办法始终是把手打湿&#xff0c;整一个能够运行&#xff0c;可以实验的东西出来。 也只有在程序开发中&#xff0c;我们才能想一个魔法师而不是魔术师&#xff0c;我们真的能够创造一个东西。而且编…