Android 淘气三千传之——Android搜索中前缀匹配的一点理解

2023-10-11 13:50

本文主要是介绍Android 淘气三千传之——Android搜索中前缀匹配的一点理解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1、前言

2、相关知识点

3、内容

4、问题

5、总结

6、参考文章 & 推荐阅读

1、前言

咳咳,当我们在浏览器、在手机的电话联系人界面等等地方,输入一段字符串之后,就可以匹配出相应前缀的结果出来(如使用 AutoCompleteTextView 输入字段就会有相应的结果匹配),在存储本地数据的时候,由于数据后期可能会变多,所以需要进行缓存或者添加数据库索引,(量级肯定不能和服务端相比),由于是需要通过前缀关键字来搜索得到结果,所以具有一定的特殊性,所以对缓存和索引的知识点简单地梳理了一下。

2、相关知识点

我们的目的都是为了提高数据检索效率,既然是前缀,符合这个特征的,映入脑海的首先是 Trie 了,同时,我们需要考虑的还有空间时间,涉及到的一共有以下知识点:

  • Trie
  • Hash Tree
  • 索引
  • 三叉树 (Ternary Search Trie)
  • 番外:fm-index

3、内容

1) Trie (前缀树、字典树)

这里写图片描述

注:图片来自 http://www.sciencedirect.com/science/article/pii/S1570866703000662

Trie 作为比较常见的数据结构,包含了以下特点:

  • 根为空,不包含字符
  • 从根到某一个节点连接起来是一个字符串
  • 插入时间为 O(n) n 是字符串长度

我们可以尝试写一个简单的Trie,构造的 Trie 如下:

public class TrieNode {public int path; // 多少个字符串有经过这个节点public int end;  // 多少个字符串以这个节点结束public TrieNode[] map;public TrieNode() {path = 0;end = 0;map = new TrieNode[26];}
}
public class Trie {private TrieNode root;private List<String> result;private StringBuilder stringBuilder = new StringBuilder();public Trie() {root = new TrieNode();}public void insert(String word) {if (word == null) {return;}char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (node.map[index] == null) {node.map[index] = new TrieNode();}node = node.map[index];node.path++;}node.end++;}public List<String> searchStr(String word) {if (word == null) {return null;}char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';stringBuilder.append(chs[i]);if (node.map[index] == null)return null;node = node.map[index];}if (node.path != 0) {result = new ArrayList<>();if (node.end != 0)result.add(stringBuilder.toString());getStr(node);return result;} else {return null;}}//通过 DFS 对树进行搜索private 

这篇关于Android 淘气三千传之——Android搜索中前缀匹配的一点理解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/188493

相关文章

Android使用ImageView.ScaleType实现图片的缩放与裁剪功能

《Android使用ImageView.ScaleType实现图片的缩放与裁剪功能》ImageView是最常用的控件之一,它用于展示各种类型的图片,为了能够根据需求调整图片的显示效果,Android提... 目录什么是 ImageView.ScaleType?FIT_XYFIT_STARTFIT_CENTE

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

Android实现两台手机屏幕共享和远程控制功能

《Android实现两台手机屏幕共享和远程控制功能》在远程协助、在线教学、技术支持等多种场景下,实时获得另一部移动设备的屏幕画面,并对其进行操作,具有极高的应用价值,本项目旨在实现两台Android手... 目录一、项目概述二、相关知识2.1 MediaProjection API2.2 Socket 网络

Android实现悬浮按钮功能

《Android实现悬浮按钮功能》在很多场景中,我们希望在应用或系统任意界面上都能看到一个小的“悬浮按钮”(FloatingButton),用来快速启动工具、展示未读信息或快捷操作,所以本文给大家介绍... 目录一、项目概述二、相关技术知识三、实现思路四、整合代码4.1 Java 代码(MainActivi

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》:本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32

深入理解Apache Kafka(分布式流处理平台)

《深入理解ApacheKafka(分布式流处理平台)》ApacheKafka作为现代分布式系统中的核心中间件,为构建高吞吐量、低延迟的数据管道提供了强大支持,本文将深入探讨Kafka的核心概念、架构... 目录引言一、Apache Kafka概述1.1 什么是Kafka?1.2 Kafka的核心概念二、Ka

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地