网站开发和运作的财务预算,太原seo建站,做电影资源网站服务器怎么选,宁德市房价首先我们将对代码进行基础构思#xff1a;
一、 创建TrieNode 类
Trie 树的节点类#xff0c;用于构建 Trie 树。TrieNode 类有以下成员变量#xff1a; children#xff1a;一个 Map#xff0c;用于存储当前节点的子节点#xff0c;key 是字符#xff0c;value 是对应…首先我们将对代码进行基础构思
一、 创建TrieNode 类
Trie 树的节点类用于构建 Trie 树。TrieNode 类有以下成员变量 children一个 Map用于存储当前节点的子节点key 是字符value 是对应的子节点 TrieNode。 isEndOfWord布尔值表示当前节点是否是一个关键词的结尾。 fail失败指针指向其他节点用于构建 Trie 树的失败指针。 matchedKeywords一个 Set用于存储匹配到的关键词。
/*** Trie树节点类*/
class TrieNode {MapCharacter, TrieNode children; // 子节点映射表boolean isEndOfWord; // 是否是关键词结尾TrieNode fail; // 失败指针指向其他节点SetString matchedKeywords; // 匹配到的关键词集合public TrieNode() {children new HashMap();isEndOfWord false;fail null;matchedKeywords new HashSet();}
}二 、创建Trie 类
Trie 类用于构建 Trie 树并实现相关功能。Trie 类有以下成员变量 rootTrie 树的根节点。 Trie 类有以下成员方法 insert(String word) 将一个关键词插入到 Trie 树中。在插入过程中逐个字符遍历如果当前字符不存在对应的子节点则创建一个新的节点并插入如果当前字符已存在对应的子节点则直接获取子节点继续遍历。最后标记当前节点为关键词结尾并将该关键词添加到节点的 matchedKeywords 集合中。 buildFailPointers()构建 Trie 树的失败指针。通过 BFS 遍历 Trie 树为每个节点设置失败指针使得在搜索过程中可以快速回溯失败节点从而实现 KMP 算法的功能。同时也将匹配到的关键词集合合并到当前节点的 matchedKeywords 中。 search(String text)在文本中搜索关键词。根据 Trie 树逐个字符遍历文本并根据失败指针快速回溯找到匹配的关键词。
/*** Trie树类*/
class Trie {private TrieNode root;public Trie() {root new TrieNode();}/*** 插入关键词到Trie树* param word*/public void insert(String word) {TrieNode current root;for (char ch : word.toCharArray()) {current.children.putIfAbsent(ch, new TrieNode());current current.children.get(ch);}current.isEndOfWord true;current.matchedKeywords.add(word);}/*** 构建Trie树的失败指针用于KMP算法*/public void buildFailPointers() {QueueTrieNode queue new LinkedList();for (TrieNode child : root.children.values()) {child.fail root;queue.add(child);}while (!queue.isEmpty()) {TrieNode current queue.poll();for (Map.EntryCharacter, TrieNode entry : current.children.entrySet()) {char ch entry.getKey();TrieNode child entry.getValue();TrieNode failNode current.fail;while (failNode ! null !failNode.children.containsKey(ch)) {failNode failNode.fail;}if (failNode null) {child.fail root;} else {child.fail failNode.children.get(ch);child.matchedKeywords.addAll(child.fail.matchedKeywords); // 合并匹配关键词集合}queue.add(child);}}}三. 创建ChineseKeywordMatcher 类
ChineseKeywordMatcher 类是程序的入口点负责读取用户输入的文本并进行匹配。 ChineseKeywordMatcher 类有以下成员方法 在主方法main中我们定义了多组关键词构建 Trie 树并插入关键词然后构建失败指针接着获取用户输入的文本最后通过并行计算搜索组合关键词并输出匹配的结果。 searchCombinationsParallel(String text, ListList keywordGroups)并行计算搜索组合关键词并返回匹配的组合关键词集合。在这个方法中我们使用线程池来同时搜索多组关键词从而提高搜索效率。 generateCombinations(String text, List keywords, StringBuilder currentCombination, Set matchedKeywords)生成所有组合关键词并在文本中查找匹配。这是一个辅助方法在主方法中调用并通过非递归方式生成组合关键词然后根据 Trie 树在文本中查找匹配。 public static void main(String[] args) throws InterruptedException, ExecutionException {// 定义多组关键词ListListString keywordGroups new ArrayList();keywordGroups.add(Arrays.asList(人工智能, AI));keywordGroups.add(Arrays.asList(隐私计算, 联邦学习, 可信执行环境));// 创建Trie树并插入关键词Trie trie new Trie();for (ListString keywords : keywordGroups) {for (String keyword : keywords) {trie.insert(keyword);}}// 构建Trie树的失败指针用于KMP算法trie.buildFailPointers();// 获取用户输入的文本Scanner scanner new Scanner(System.in);System.out.print(请输入中文文本);String userInput scanner.nextLine();scanner.close();// 并行计算搜索组合关键词并返回匹配的组合关键词集合SetString matchedCombinationKeywords searchCombinationsParallel(userInput, keywordGroups);if (!matchedCombinationKeywords.isEmpty()) {System.out.println(匹配的组合关键词);for (String keyword : matchedCombinationKeywords) {System.out.println(keyword);}} else {System.out.println(没有匹配到组合关键词。);}}
四、 输入文本
在代码的 main 方法中通过 Scanner 读取用户输入的中文文本。 // 获取用户输入的文本Scanner scanner new Scanner(System.in);System.out.print(请输入中文文本);String userInput scanner.nextLine();scanner.close(); 注意这里有部分长字符串需要剔除空格才可以精准匹配 五、 匹配组合关键词
在 searchCombinationsParallel 方法中我们使用线程池和并行计算来搜索多组关键词的组合关键词。在 generateCombinations 方法中我们通过非递归方式生成组合关键词并利用 Trie 树在文本中查找匹配。最终输出匹配到的组合关键词。 /*** 并行计算在文本中搜索组合关键词并返回匹配的组合关键词集合* param text* param keywordGroups* return* throws InterruptedException* throws ExecutionException*/public static SetString searchCombinationsParallel(String text, ListListString keywordGroups) throws InterruptedException, ExecutionException {// 获取可用处理器核心数并创建对应数量的线程池int numThreads Runtime.getRuntime().availableProcessors();ExecutorService executorService Executors.newFixedThreadPool(numThreads);// 使用线程安全的集合来保存匹配结果SetString matchedCombinationKeywords new ConcurrentSkipListSet();// 创建并行任务列表ListCallableSetString tasks new ArrayList();for (ListString keywords : keywordGroups) {tasks.add(() - {SetString matchedKeywords new HashSet();generateCombinations(text, keywords, new StringBuilder(), matchedKeywords);return matchedKeywords;});}// 并行执行任务获取结果并合并到结果集合ListFutureSetString futures executorService.invokeAll(tasks);for (FutureSetString future : futures) {matchedCombinationKeywords.addAll(future.get());}// 关闭线程池executorService.shutdown();return matchedCombinationKeywords;}/*** 生成所有组合关键词并在文本中查找匹配* param text* param keywords* param currentCombination* param matchedKeywords*/private static void generateCombinations(String text, ListString keywords, StringBuilder currentCombination, SetString matchedKeywords) {int[] indices new int[keywords.size()]; // 记录每组关键词的索引while (true) {StringBuilder currentCombinationKeyword new StringBuilder();// 生成当前的组合关键词for (int i 0; i keywords.size(); i) {String keyword keywords.get(i);// int index indices[i];if (currentCombinationKeyword.length() 0) {currentCombinationKeyword.append(,);}currentCombinationKeyword.append(keyword);indices[i];}Trie trie new Trie();for (String keyword : currentCombinationKeyword.toString().split(,)) {trie.insert(keyword);}trie.buildFailPointers();SetString matched trie.search(text);if (!matched.isEmpty()) {matchedKeywords.addAll(matched);}// 移动索引类似组合数学中的组合生成算法int j keywords.size() - 1;while (j 0 indices[j] keywords.size()) {indices[j] 0;j--;}if (j 0) {break;}}}根据以上步骤思路我们编写完整代码具体完整代码如下所示
package cn.konne.konneim.download;
import java.util.*;
import java.util.concurrent.*;/*** Trie树节点类*/
class TrieNode {MapCharacter, TrieNode children; // 子节点映射表boolean isEndOfWord; // 是否是关键词结尾TrieNode fail; // 失败指针指向其他节点SetString matchedKeywords; // 匹配到的关键词集合public TrieNode() {children new HashMap();isEndOfWord false;fail null;matchedKeywords new HashSet();}
}/*** Trie树类*/
class Trie {private TrieNode root;public Trie() {root new TrieNode();}/*** 插入关键词到Trie树* param word*/public void insert(String word) {TrieNode current root;for (char ch : word.toCharArray()) {current.children.putIfAbsent(ch, new TrieNode());current current.children.get(ch);}current.isEndOfWord true;current.matchedKeywords.add(word);}/*** 构建Trie树的失败指针用于KMP算法*/public void buildFailPointers() {QueueTrieNode queue new LinkedList();for (TrieNode child : root.children.values()) {child.fail root;queue.add(child);}while (!queue.isEmpty()) {TrieNode current queue.poll();for (Map.EntryCharacter, TrieNode entry : current.children.entrySet()) {char ch entry.getKey();TrieNode child entry.getValue();TrieNode failNode current.fail;while (failNode ! null !failNode.children.containsKey(ch)) {failNode failNode.fail;}if (failNode null) {child.fail root;} else {child.fail failNode.children.get(ch);child.matchedKeywords.addAll(child.fail.matchedKeywords); // 合并匹配关键词集合}queue.add(child);}}}/*** 在文本中搜索关键词并返回匹配的关键词集合* param text 要匹配得文本串* return*/public SetString search(String text) {TrieNode current root;SetString matchedKeywords new HashSet();StringBuilder matchedKeyword new StringBuilder();for (char ch : text.toCharArray()) {while (current ! root !current.children.containsKey(ch)) {current current.fail;}if (current.children.containsKey(ch)) {current current.children.get(ch);matchedKeyword.append(ch);if (current.isEndOfWord) {matchedKeywords.addAll(current.matchedKeywords);}} else {current root;matchedKeyword.setLength(0);}}return matchedKeywords;}
}public class ChineseKeywordMatcher {public static void main(String[] args) throws InterruptedException, ExecutionException {// 定义多组关键词ListListString keywordGroups new ArrayList();keywordGroups.add(Arrays.asList(人工智能, AI));keywordGroups.add(Arrays.asList(隐私计算, 联邦学习, 可信执行环境));// 创建Trie树并插入关键词Trie trie new Trie();for (ListString keywords : keywordGroups) {for (String keyword : keywords) {trie.insert(keyword);}}// 构建Trie树的失败指针用于KMP算法trie.buildFailPointers();// 获取用户输入的文本Scanner scanner new Scanner(System.in);System.out.print(请输入中文文本);String userInput scanner.nextLine();scanner.close();// 并行计算搜索组合关键词并返回匹配的组合关键词集合SetString matchedCombinationKeywords searchCombinationsParallel(userInput, keywordGroups);if (!matchedCombinationKeywords.isEmpty()) {System.out.println(匹配的组合关键词);for (String keyword : matchedCombinationKeywords) {System.out.println(keyword);}} else {System.out.println(没有匹配到组合关键词。);}}/*** 并行计算在文本中搜索组合关键词并返回匹配的组合关键词集合* param text* param keywordGroups* return* throws InterruptedException* throws ExecutionException*/public static SetString searchCombinationsParallel(String text, ListListString keywordGroups) throws InterruptedException, ExecutionException {// 获取可用处理器核心数并创建对应数量的线程池int numThreads Runtime.getRuntime().availableProcessors();ExecutorService executorService Executors.newFixedThreadPool(numThreads);// 使用线程安全的集合来保存匹配结果SetString matchedCombinationKeywords new ConcurrentSkipListSet();// 创建并行任务列表ListCallableSetString tasks new ArrayList();for (ListString keywords : keywordGroups) {tasks.add(() - {SetString matchedKeywords new HashSet();generateCombinations(text, keywords, new StringBuilder(), matchedKeywords);return matchedKeywords;});}// 并行执行任务获取结果并合并到结果集合ListFutureSetString futures executorService.invokeAll(tasks);for (FutureSetString future : futures) {matchedCombinationKeywords.addAll(future.get());}// 关闭线程池executorService.shutdown();return matchedCombinationKeywords;}/*** 生成所有组合关键词并在文本中查找匹配 * param text* param keywords* param currentCombination* param matchedKeywords*/private static void generateCombinations(String text, ListString keywords, StringBuilder currentCombination, SetString matchedKeywords) {int[] indices new int[keywords.size()]; // 记录每组关键词的索引while (true) {StringBuilder currentCombinationKeyword new StringBuilder();// 生成当前的组合关键词for (int i 0; i keywords.size(); i) {String keyword keywords.get(i);// int index indices[i];if (currentCombinationKeyword.length() 0) {currentCombinationKeyword.append(,);}currentCombinationKeyword.append(keyword);indices[i];}Trie trie new Trie();for (String keyword : currentCombinationKeyword.toString().split(,)) {trie.insert(keyword);}trie.buildFailPointers();SetString matched trie.search(text);if (!matched.isEmpty()) {matchedKeywords.addAll(matched);}// 移动索引类似组合数学中的组合生成算法int j keywords.size() - 1;while (j 0 indices[j] keywords.size()) {indices[j] 0;j--;}if (j 0) {break;}}}
}
以上为java关键词组匹配程序如果有啥不足欢迎支持
