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

图片来源：

Opensource.com

我从事商业软件设计和开发已有 30 多年，我很高兴地宣布，我的部分软件首次以新的开源项目形式发布。对于戴尔的开源项目而言，这是一个名为 Mensa 的 Java 项目。

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

Mensa 简述

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

Mensa 的效率很高，因为它只需一次扫描即可快速处理源文本，无论它是搜索一个关键字还是一百万个关键字。

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

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

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

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

因此，在 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 定义的任何类型的符号。因此，可以创建一个机器来匹配字节、字符、整数、基因序列、位序列等。

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

在非常高的层面上，基于 Mensa 的此问题解决方案如下所示：

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

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

这对于昵称尤其重要——例如，公司中很容易有多个“Andy”。这样，每次匹配机器报告匹配时，您不仅会知道匹配的文本，还会知道被提及的具体员工。