使用 Mensa 构建更好的匹配解决方案

图片来源：

Opensource.com

我设计和开发商业软件已经超过 30 年了，我很高兴地宣布，我的部分软件首次以新的开源项目形式发布。对于 Dell 的开源，这是一个名为 Mensa 的 Java 项目。

Mensa 是一个 Java 类库。因此，Mensa 的主要用户是使用 Java 的程序员。但是，我目前正在参与一个团队，该团队正在使用 C# 中的 Mensa（使用 IKVM.NET），但这将在以后讨论。如果您对此特别感兴趣，请随时与我联系。

Mensa 简述

Mensa 为一类模式匹配问题提供了一个强大而有效的解决方案。具体来说，Mensa 可以轻松地在源文本中查找任何或所有关键字。例如，在小说（源文本）中查找对已命名角色的所有引用（关键字）。

Mensa 的效率很高，无论是在搜索一个关键字还是一百万个关键字，它都可以在一次传递中快速处理源文本。

Mensa 是通用的，因为它不仅限于匹配文本数据。相反，根据定义，源文本是任意长度的符号序列。这些符号的实际数据类型可以是任何东西——字符、字节、数字、象形文字、音符、核苷酸等。

多年来，从 Quest Software 开始，并在 Dell Software（公司收购后）继续，Mensa 的核心贡献者一直在致力于平台技术，以发现、映射和集成各种企业信息源中原本断开连接的数据。这种解决方案的一个关键要素是准确高效地查找内容的能力。

最近，我们专注于交付自动数字资产分类技术，例如 Dell One Identity Manager 数据治理版的分类模块使用的技术。

我们一直在使用获得许可的第三方软件进行基于词典的关键字搜索，但由于各种原因，我们知道最终需要替换该组件。大约一年前，我们开始寻找开源替代方案。但是，没有可用的开源解决方案具有我们正在寻找的所有要素：泛型、灵活性、模糊匹配、大型词典效率等。

因此，在 2014 年初，我开始创建一个新的“Java Aho-Corasick 库”，以满足所有这些要求。后来，我们将名称更改为“Mensa”。

标准 Java 库包含对在字符串中查找特定模式的支持。有两种基本机制可供选择

字符串搜索 在另一个字符串中查找文字字符串值的实例。例如，您可以在文本“Welcome to Ann Arbor”中搜索单词“Arbor”。结果将表明该词位于位置 15（Java 从零开始计数）。
正则表达式匹配在另一个字符串中查找字符串模式的实例。例如，您可以在“Welcome to Ann Arbor”中搜索模式“A...r”。模式中的“.”表示“任何字符”，因此也会在位置 15 找到匹配项。

在许多情况下，这些内置的 Java 功能可以正常工作——但并非总是如此。考虑以下问题场景

标准库函数对内存中的字符串进行操作。它们不太适合搜索不易完全放入内存的非常大的文本。
内置的正则表达式可以识别单词边界，但需要比简单的字符串文字匹配（无法识别单词边界）花费更多的处理时间。例如，如果不考虑单词边界，“boy”将在“30-day boycott”中匹配，这通常不是您想要的。
标准库函数无法很好地扩展以查找大量关键字。您的选择是
- 对每个关键字执行单独的文字（或正则表达式）搜索操作
- 创建一个包含每个关键字的替代子句的正则表达式。

随着关键字数量的增加，这些方法的性能会受到影响。标准库函数仅限于在字符文本中查找字符关键字。例如，无法使用内置函数查找包含 1000 万个整数的数组中的所有“317、206、827、1106”序列。

分别使用 Mensa 可以轻松处理每个场景

- Mensa 在抽象文本源上运行。针对内存中和流式文本源提供了实现。此外，可以轻松地为自定义源创建新的文本源实现。例如，您可以创建一个从数据库、版本控制系统、REST API 等读取的文本源。
- Mensa 具有启用或禁用单词边界检查的选项。启用后，仅当由单词边界符号分隔时才识别关键字。什么构成单词边界符号由抽象符号分类器确定。提供了字符符号的实现，但您也可以创建自定义符号分类器。例如，基因搜索应用程序可以将某些核苷酸定义为基因边界。
- 构建 Mensa 机器后，其性能仅取决于正在搜索的文本的长度，而不是关键字的数量。给定的机器实例可以多次使用，甚至可以由并发线程使用，以搜索多个文本源。
- Mensa 使用 Java 泛型实现。因此，它可以用于匹配 Java 模板类型 S 定义的任何类型的符号。因此，可以创建一个机器来匹配字节、字符、整数、基因序列、位序列等。

假设您的公司有一个内部公司 Web 门户，其中包含数千个网页。您被要求编写一个程序来确定每个员工在该门户网站中的任何位置被提及的次数。您可以访问 HR 数据库，其中包含公司中每个员工的姓名，有时还包含昵称，大约有 25,000 名员工。

在很高的层面上，基于 Mensa 的解决方案看起来像这样

- 1. 创建一个 Mensa 关键字集合。
  2. 从 HR 数据库中读取员工的姓名和昵称，并将每个都添加到关键字集合中。
  3. 创建一个 Mensa 匹配机器。
  4. 使用关键字集合初始化它。
  5. 对于 Web 门户中的每个页面，创建一个基于该页面的 Mensa 文本源，然后针对该源运行匹配机器。结果是该页面的匹配关键字（以及员工姓名或昵称）列表。

Mensa 能够将任意数据（称为用户数据）与每个关键字相关联。此附加信息包含在任何匹配结果中。对于此应用程序，使用此功能将员工身份与每个关键字一起存储会很有用。

这对于昵称尤其重要 - 例如，公司中可能不止一个“Andy”。这样，每次匹配机器报告匹配时，您不仅会知道匹配的文本，还会知道被提及的特定员工。