Lazy's Blog

深入理解最长公共子序列（Longest Common Subsequence）问题及其动态规划优化 在计算机科学中，最长公共子序列（Longest Common Subsequence, LCS） 是一个经典的动态规划（Dynamic Programming, DP）问题。它在文本比较、版本控制、基因序列分析、自然语言处理等领域有广泛的应用。本文将详细介绍如何使用动态规划解决LCS问题，并进一步探讨两种优化方法，以减少算法的空间复杂度。此外，我们还将介绍如何回溯得到实际的LCS序列，并讨论相关的应用场景。 问题描述 题目编号：1143. 最长公共子序列 题目内容 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。 定义： 子序列（Subsequence）：一个字符串的子序列是指这样一个新的字符串，它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是。 公共子序列（Common...

NLTK 使用指南：手动安装 punkt 数据文件（包括 punkt_tab.zip） 在使用 Python 的自然语言处理库 NLTK 时，可能会遇到无法通过 nltk.download('punkt') 正常下载数据文件的问题。本文将详细讲解如何手动下载、安装 punkt 和 punkt_tab 数据文件，并确保其在本地环境中能够正确使用。 问题 当你尝试使用 NLTK 中的 word_tokenize 函数时，可能会遇到以下错误信息： 1LookupError: Resource punkt not found. 该错误通常是因为 punkt 数据文件没有正确下载或安装。punkt 是 NLTK 库中用于分词的模型，需要在本地下载并正确配置。此时，我们可以手动下载并配置它。 解决方案 一、下载 nltk_data-gh-pages.zip 数据文件 首先，我们需要下载 nltk_data 数据文件，具体步骤如下： 访问下载链接： 打开 Gitee 上的 nltk_data 页面，点击页面上的 克隆下载 按钮，然后选择 下载 ZIP 选项，开始下载...

解决 Hugging Face Datasets 中 ROUGE 指标加载问题 在使用 Hugging Face Datasets 库时，可能会遇到无法从远程 GitHub 下载 ROUGE 指标脚本的问题。默认情况下，load_metric("rouge") 会尝试从远程仓库下载指标脚本，如果网络连接出现问题，可能会导致加载失败。以下是几种解决方法，可以避免依赖网络连接，确保指标脚本的正常加载。 1. 强制使用本地缓存 load_metric("rouge") 默认会首先检查本地缓存，如果本地缓存中已有该指标脚本，它会直接加载；如果没有，则会尝试从远程仓库下载。如果希望避免每次都尝试远程下载，可以直接指定本地缓存路径加载指标脚本。 代码示例： 1234from datasets import load_metric# 使用本地路径加载 ROUGE 指标metric =...

1. KMP 算法介绍 KMP 算法：全称 「Knuth Morris Pratt 算法」，由 Donald Knuth、James H. Morris、Vaughan Pratt 在 1977 年联合发表。 KMP 算法思想：对于给定文本串 TTT 和模式串 PPP，当发现文本串的某个字符与模式串失配时，利用模式串的部分匹配信息尽量减少匹配次数，避免文本串的指针回退。 1.1 朴素匹配算法的缺陷 在朴素匹配算法中，分别用指针 iii 和 jjj 表示文本串 TTT 和模式串 PPP 的当前匹配位置。当字符失配时： jjj 回退到起始位置； iii 回退到匹配开始位置的下一个字符，重新进行匹配。 示例图展示了朴素匹配算法的过程（失配后重新尝试从下一字符开始匹配）： 在这种情况下，如果匹配字符较多且发生多次失配，匹配效率会很低。 1.2 KMP 算法的改进 KMP 算法通过预处理模式串 PPP，构造一个 前缀表（lps 表），在匹配过程中借助前缀表的信息优化模式串指针的移动，使得主串指针 iii 无需回退。 以示例为例： 模式串 P 在匹配时，若在...