当前位置: 首页 > news >正文

C#,动态规划问题中基于单词搜索树(Trie Tree)的单词断句分词( Word Breaker)算法与源代码

1 分词

分词是自然语言处理的基础,分词准确度直接决定了后面的词性标注、句法分析、词向量以及文本分析的质量。英文语句使用空格将单词进行分隔,除了某些特定词,如how many,New York等外,大部分情况下不需要考虑分词问题。但有些情况下,没有空格,则需要好的分词算法。

简单的分词算法主要有:

2 正向最大匹配

从左到右尽可能划分出一段连续字符,使得其等于词典中的某个词,然后将这段连续字符提取出来,对余下的部分进行同样的操作。如果第一个字符不是词典中任何一个词的前缀,那么这个字符单独作为一个词。

3 逆向最大匹配

跟正向最大匹配的唯一不同是从右到左尽可能划分出一段连续字符。

4 双向最大匹配

歧义指对于一个句子有多个分词结果。汉语文本中 90.0%左右的句子,FMM 和 BMM 的切分完全重合且正确,9.0%左右的句子 FMM 和 BMM 切分不同,但其中必有一个是正确的(歧义检测成功),只有不到1.0 %的句子,或者 FMM 和 BMM 的切分虽重合却是错的,或者FMM 和 BMM 切分 不同但两个都不对(歧义检测失败)。
 

本文介绍了基于单词搜索树(Trie Tree)的单词断句分词( Word Breaker)算法及其源代码。

5 节点信息

public class TrieNode
{public TrieNode[] children { get; set; } = new TrieNode[26];// isEndOfWord is true if the node represents// end of a wordpublic bool isEndOfWord { get; set; } = false;public TrieNode(){isEndOfWord = false;for (int i = 0; i < 26; i++){children[i] = null;}}
}

public class TrieNode
{
    public TrieNode[] children { get; set; } = new TrieNode[26];

    // isEndOfWord is true if the node represents
    // end of a word
    public bool isEndOfWord { get; set; } = false;

    public TrieNode()
    {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++)
        {
            children[i] = null;
        }
    }
}

6 字典分词算法

using System;
using System.Text;namespace Legalsoft.Truffer.Algorithm
{public static class Trie_Tree_Word_Breaker{public static void Insert(TrieNode root, string key){TrieNode pCrawl = root;for (int i = 0; i < key.Length; i++){int index = key[i] - 'a';if (pCrawl.children[index] == null){pCrawl.children[index] = new TrieNode();}pCrawl = pCrawl.children[index];}pCrawl.isEndOfWord = true;}public static bool Search(TrieNode root, string key){TrieNode pCrawl = root;for (int i = 0; i < key.Length; i++){int index = key[i] - 'a';if (pCrawl.children[index] == null){return false;}pCrawl = pCrawl.children[index];}return (pCrawl != null && pCrawl.isEndOfWord);}public static bool Word_Break(string str, TrieNode root){int size = str.Length;if (size == 0){return true;}for (int i = 1; i <= size; i++){if (Search(root, str.Substring(0, i)) && Word_Break(str.Substring(i, size - i), root)){return true;}}return false;}public static string Drive(){string[] dictionary = {"mobile", "huawei","sam", "sung", "ma","mango", "icecream","and", "go", "i", "like","ice", "cream" };int n = dictionary.Length;TrieNode root = new TrieNode();// Construct triefor (int i = 0; i < n; i++){Insert(root, dictionary[i]);}StringBuilder sb = new StringBuilder();sb.AppendLine(Word_Break("ilikehuawei", root) + "<br>");sb.AppendLine(Word_Break("iiiiiiii", root) + "<br>");sb.AppendLine(Word_Break("", root) + "<br>");sb.AppendLine(Word_Break("ilikelikeimangoiii", root) + "<br>");sb.AppendLine(Word_Break("huaweiandmango", root) + "<br>");sb.AppendLine(Word_Break("huaweiandmangok", root) + "<br>");return sb.ToString();}}
}

using System;
using System.Text;

namespace Legalsoft.Truffer.Algorithm
{
    public static class Trie_Tree_Word_Breaker
    {
        public static void Insert(TrieNode root, string key)
        {
            TrieNode pCrawl = root;

            for (int i = 0; i < key.Length; i++)
            {
                int index = key[i] - 'a';
                if (pCrawl.children[index] == null)
                {
                    pCrawl.children[index] = new TrieNode();
                }
                pCrawl = pCrawl.children[index];
            }

            pCrawl.isEndOfWord = true;
        }

        public static bool Search(TrieNode root, string key)
        {
            TrieNode pCrawl = root;
            for (int i = 0; i < key.Length; i++)
            {
                int index = key[i] - 'a';
                if (pCrawl.children[index] == null)
                {
                    return false;
                }
                pCrawl = pCrawl.children[index];
            }
            return (pCrawl != null && pCrawl.isEndOfWord);
        }

        public static bool Word_Break(string str, TrieNode root)
        {
            int size = str.Length;

            if (size == 0)
            {
                return true;
            }
            for (int i = 1; i <= size; i++)
            {
                if (Search(root, str.Substring(0, i)) && Word_Break(str.Substring(i, size - i), root))
                {
                    return true;
                }
            }

            return false;
        }

        public static string Drive()
        {
            string[] dictionary = {
                "mobile", "huawei",
                "sam", "sung", "ma",
                "mango", "icecream",
                "and", "go", "i", "like",
                "ice", "cream" 
            };

            int n = dictionary.Length;
            TrieNode root = new TrieNode();

            // Construct trie
            for (int i = 0; i < n; i++)
            {
                Insert(root, dictionary[i]);
            }

            StringBuilder sb = new StringBuilder();
            sb.AppendLine(Word_Break("ilikehuawei", root) + "<br>");
            sb.AppendLine(Word_Break("iiiiiiii", root) + "<br>");
            sb.AppendLine(Word_Break("", root) + "<br>");
            sb.AppendLine(Word_Break("ilikelikeimangoiii", root) + "<br>");
            sb.AppendLine(Word_Break("huaweiandmango", root) + "<br>");
            sb.AppendLine(Word_Break("huaweiandmangok", root) + "<br>");
            return sb.ToString();
        }
    }
}
 

相关文章:

C#,动态规划问题中基于单词搜索树(Trie Tree)的单词断句分词( Word Breaker)算法与源代码

1 分词 分词是自然语言处理的基础&#xff0c;分词准确度直接决定了后面的词性标注、句法分析、词向量以及文本分析的质量。英文语句使用空格将单词进行分隔&#xff0c;除了某些特定词&#xff0c;如how many&#xff0c;New York等外&#xff0c;大部分情况下不需要考虑分词…...

计算机网络(六)应用层

6.1、应用层概述 我们在浏览器的地址中输入某个网站的域名后&#xff0c;就可以访问该网站的内容&#xff0c;这个就是万维网WWW应用&#xff0c;其相关的应用层协议为超文本传送协议HTTP 用户在浏览器地址栏中输入的是“见名知意”的域名&#xff0c;而TCP/IP的网际层使用IP地…...

上海亚商投顾:沪指探底回升微涨 机器人概念股午后爆发

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 市场全天探底回升&#xff0c;沪指盘中跌超1.6%&#xff0c;创业板指一度跌逾3%&#xff0c;午后集体拉升翻红…...

conda相关操作

conda 是一个开源的包管理和环境管理工具&#xff0c;主要用于 Python 和数据科学领域。它可以帮助用户安装、更新、删除和管理软件包&#xff0c;同时支持创建和管理虚拟环境。以下是关于 conda 的所有常见操作&#xff1a; 1. 安装 Conda Conda 通常通过安装 Anaconda 或 Mi…...

使用TCP协议实现智能聊天机器人

实验目的与要求 本实验是程序设计类实验&#xff0c;要求使用原始套接字编程&#xff0c;掌握TCP/IP协议与网络编程Sockets通信模型&#xff0c;并根据教师给定的任务要求&#xff0c;使用TCP协议实现智能聊天机器人。 &#xff08;1&#xff09;熟悉标准库socket 的用法。 …...

PHP二维数组去除重复值

Date: 2025.01.07 20:45:01 author: lijianzhan PHP二维数组内根据ID或者名称去除重复值 代码示例如下&#xff1a; // 假设 data数组如下 $data [[id > 1, name > Type A],[id > 2, name > Type B],[id > 1, name > Type A] // 重复项 ];// 去重方法 $dat…...

2025年01月11日Github流行趋势

项目名称&#xff1a;xiaozhi-esp32 项目地址url&#xff1a;https://github.com/78/xiaozhi-esp32项目语言&#xff1a;C历史star数&#xff1a;2433今日star数&#xff1a;321项目维护者&#xff1a;78, MakerM0, whble, nooodles2023, Kevincoooool项目简介&#xff1a;构建…...

备战蓝桥杯 队列和queue详解

目录 队列的概念 队列的静态实现 总代码 stl的queue 队列算法题 1.队列模板题 2.机器翻译 3.海港 双端队列 队列的概念 和栈一样&#xff0c;队列也是一种访问受限的线性表&#xff0c;它只能在表头位置删除&#xff0c;在表尾位置插入&#xff0c;队列是先进先出&…...

IT面试求职系列主题-Jenkins

想成功求职&#xff0c;必要的IT技能一样不能少&#xff0c;先说说Jenkins的必会知识吧。 1) 什么是Jenkins Jenkins 是一个用 Java 编写的开源持续集成工具。它跟踪版本控制系统&#xff0c;并在发生更改时启动和监视构建系统。 2&#xff09;Maven、Ant和Jenkins有什么区别…...

Vue篇-06

1、路由简介 vue-rooter&#xff1a;是vue的一个插件库&#xff0c;专门用来实现SPA应用 1.1、对SPA应用的理解 1、单页 Web 应用&#xff08;single page web application&#xff0c;SPA&#xff09;。 2、整个应用只有一个完整的页面 index.html。 3、点击页面中的导航链…...

mysql binlog 日志分析查找

文章目录 前言一、分析 binlog 内容二、编写脚本结果总结 前言 高效快捷分析 mysql binlog 日志文件。 mysql binlog 文件很大 怎么快速通过关键字查找内容 一、分析 binlog 内容 通过 mysqlbinlog 命令可以看到 binlog 解析之后的大概样子 二、编写脚本 编写脚本 search_…...

ubuntu 配置OpenOCD与RT-RT-thread环境的记录

1.git clone git://git.code.sf.net/p/openocd/code openocd 配置gcc编译环境 2. sudo gedit /etc/apt/source.list #cdrom sudo apt-get install git sudo apt-get install libtool-bin sudo apt-get install pkg-config sudo apt-install libusb-1.0-0-dev sudo apt-get…...

双系统解决开机提示security Policy Violation的方法

最近&#xff0c;Windows系统更新后&#xff0c;发现电脑开机无法进入桌面&#xff0c;显示“Verifiying shim SBAT data failed: security Policy Violation; So mething has gone seriously Wrong: SBAT self-check failed: Security Policy Violation”的英文错误信息。为了…...

附加共享数据库( ATTACH DATABASE)的使用场景

附加共享数据库&#xff08;使用 ATTACH DATABASE&#xff09;的功能非常实用&#xff0c;通常会在以下几种场景下需要用到&#xff1a; 1. 跨数据库查询和分析 场景&#xff1a; 你的公司有两个独立的数据库&#xff1a; 一个存储了学生信息 (school.db)一个存储了员工信息 …...

matlab的绘图的标题中(title)添加标量以及格式化输出

有时候我们需要在matlab绘制的图像的标题中添加一些变量&#xff0c;这样在修改某些参数后&#xff0c;标题会跟着一块儿变。可以采用如下的方法&#xff1a; x -10:0.1:10; %x轴的范围 mu 0; %均值 sigma 1; %标准差 y normpdf(x,mu,sigma); %使用normpdf函数生成高斯函数…...

2、第一个GO 程序

引言 接下里我们就用Go Land 工具&#xff0c;开发第一个GO程序。大家也可以用其他的开发工具&#xff0c;例如 Vs Code 1、新建项目 第一个是选择你的程序保存位置 &#xff08;不要有中文&#xff09;。 第二个是你的Go的编译器的安装地址。 选择完毕后&#xff0c;就点击 …...

【Linux-多线程】-线程安全单例模式+可重入vs线程安全+死锁等

一、线程安全的单例模式 什么是单例模式 单例模式是一种“经典的&#xff0c;常用的&#xff0c;常考的”设计模式 什么是设计模式 IT行业这么火&#xff0c;涌入的人很多.俗话说林子大了啥鸟都有。大佬和菜鸡们两极分化的越来越严重&#xff0c;为了让菜鸡们不太拖大佬的后…...

00000007_C语言设计模式

C语言设计模式 尽管 C 语言并不直接支持面向对象编程&#xff0c;但通过结构体和函数指针的灵活运用&#xff0c;我们依然可以实现多种经典的设计模式。 1. 工厂模式 1.1 工厂方法的定义与实现 工厂模式通过统一的接口创建对象&#xff0c;客户端无需知道具体的创建逻辑。 代…...

探索数据存储的奥秘:深入理解B树与B+树

key value 类型的数据红黑树&#xff08;最优二叉树&#xff0c;内存最优&#xff09;&#xff0c;时间复杂度&#xff1a;O&#xff08;logn&#xff09;,调整方便&#xff1b;一个结点分出两个叉B树一个节点可以分出很多叉数据量相等的条件下&#xff1a;红黑树的层数很高&am…...

Web渗透测试之XSS跨站脚本之JS输出 以及 什么是闭合标签 一篇文章给你说明白

目录 闭合标签 XSS之js输出 闭合标签 封闭标签 达到 让标签值不当成 一个属性值来展示 从而达到xss注入的效果 "> 为了想办法闭合前面的标签,不用也行成功率高一些 攻击方法 "><script>confirm(1)</script>, 其中 "> 我们称之为完成闭合…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...