regex - 用于自动完成的正则表达式

Question

我有一个短语列表，其中包含可以由空格，连字符，camelCase或PascalCase分隔的单词。我希望能够通过仅键入每个单词的几个字母，甚至跳过某些单词来过滤这些短语。
对于那些熟悉JetBrains IDE的人来说，它类似于代码完成的工作方式。我想为一般目的模拟这种行为，而不仅仅是为了在IDE中编写代码。 (一般用途是在网站上使用它来过滤短语，也许可以将其与Bash一起使用以仅通过键入文件单词的某些首字母或我所说的某些单词来获取文件列表)。这是我使用很多的非常方便的工具(在JetBrains中)!

示例:
给出以下短语:

LoremIpsumDolor

sitAmetConsectetur

adipisicing-elit-sed

Do Eiusmod Tempor incididunt

以下是一些我想过滤的典型单词:

lodo->返回LoremIpsumDolor(注意大小写不敏感，这就是我想要的方式)

dotemporinc->返回Do Eiusmod Tempor incididunt

Do->返回LoremIpsumDolor和Do Eiusmod Tempor incididunt

ac->返回sitAmetConsectetur

我一直在考虑如何实现这种功能，我能想到的最好的办法就是输入要过滤的单词-例如，示例1中的lodo将生成一个由单词字母构成的正则表达式，用一些其他表达式分隔以形成整个正则表达式...然后，它将针对该正则表达式测试列表中的每个短语，并仅返回匹配的那些短语。

我考虑过可能将单词(lodo)分解为字母，然后在每个字母之间(在开头和结尾处)放置以下正则表达式:([a-zA-Z][a-z]*)*(此解决方案，如果可以的话，假定所有短语都是骆驼\ PascalCased，但完整的解决方案也必须包括其他情况)。这将导致以下正则表达式:^([a-zA-Z][a-z]*)*[lL]([a-zA-Z][a-z]*)*[oO]([a-zA-Z][a-z]*)*[dD]([a-zA-Z][a-z]*)*[oO]([a-zA-Z][a-z]*)*$
显然，这有一些源于回溯的巨大缺陷，更具体地说，我认为(但绝对不确定)，如果我可以在([a-zA-Z][a-z]*)*中禁用内星表达式的回溯，而只保留外星的回溯，应该管用。

我希望我能很好地解释自己。也许有解决此问题的已知方法，然后我很想听听它。

Answer 1

在考虑了几个小时之后，我使用正则表达式设计了一个解决方案，我真的认为这是解决该问题的非常合适的解决方案，而且实际上并不难。

我的解决方案目前仅处理camelCase和PascalCase短语(即，它只能正确过滤用camelCase或PascalCase编写的短语)，但是将其适应其他情况应该足够容易。目前，这些情况已经足够了。

所以，这是我想出的:

给定一个单词，例如上面的示例中的lodo，您应该意识到，对于给定单词中的每个字母(l o d o)，它可以是单词的第一个字母(意味着它应该与大写字母匹配，或者如果它是第一个单词，也可能是小写字母)，或者它是我们先前发现的单词中的下一个字母(意味着它是小写字母，应该在找到前一个字母后立即尝试匹配)。
我们还应考虑正则表达式的行为，准确地说，应考虑子表达式的求值顺序。我们将使用以下事实:在or表达式(|)中，首先尝试使用左侧，而在e*?(javascript)形式的表达式中，它将找到最小的匹配项(而不是省略问号) ，在这种情况下，它将消耗最大的字符，然后我们可能会陷入回溯的状况，这对我们不利。

因此，让我们构造正则表达式。对于每个字符c，我们构造:

如果c是我们的第一个字母(在lodo中表示l)，则:

为了使c匹配第一个单词的首字母，它可以是小写字母，我们构造:(^c)

否则，它必须是另一个单词的首字母，并且必须是大写，我们构造:C

我们第一个字母的表达式:(^c|C)

否则:

我们想首先测试我们的字母是否是已经找到开头的单词的延续。同样，在这种情况下，我们的c字母(在lodo中，此参数对o，d，o中的任何一个均有效)必须为小写，然后构造(c)

否则，c必须是新单词中的第一个字母，这意味着它必须是大写字母，并且我们还必须考虑为先前字母构造的正则表达式，因此我们必须使用当前所在的整个单词，然后尝试使用其他单词，但是我们优先使用大写的c字母(希望这个解释很清楚)。对于所有情况，我们构造[a-z]*([A-Z][a-z]*)*?C。 ([a-z]*用于消耗当前单词的剩余字母，([A-Z][a-z]*)*?用于尝试消耗其他单词，如果C并非我们下一个单词的第一个字母(请记住，它可能是前面两个单词的下一个字母，依此类推...这是我的要求))

任何非首字母的表达式:(c|([a-z]*([A-Z][a-z]*)*?C))

因此，使用这些指令，我们可以为心爱的lodo构建正则表达式，这是我们应该得到的:(^l|L)(o|([a-z]*([A-Z][a-z]*)*?O))(d|([a-z]*([A-Z][a-z]*)*?D))(o|([a-z]*([A-Z][a-z]*)*?O))
我已经在AngularJS项目中用一些单词对其进行了测试，并且看起来效果很好。考虑到其他情况，我将对其进行改进，但是我认为这不会很困难。

更新

稍微玩了一下，我对它进行了调整，以考虑到我认为大多数可能的单词分隔检测情况(通过camelCase，PascalCase，空格，连字符，下划线，以及实际上不是字母字符的任何分隔符)。这使正则表达式更加简洁，甚至可能更有效率。我删除了我在原始答案中解释的大部分麻烦，并仅用[a-z]*([A-Z][a-z]*)*?替换了所有.*?子表达式，这是有效的，因为它直到选择之前都不会消耗字符，这比第一次使用字符，然后回溯。

现在，对于每个字符c，我们构造表达式:(c|.*?(C|[^a-zA-Z]c))。但是，在下一个字符为非字母字符的情况下，这可能会或可能不会引起一点回溯(取决于引擎的优化-如果它是从正则表达式构造自动机，并且将其最小化的话)。它不是所需的小写字母后的下一个字符，则它将从[^a-zA-Z]c表达式返回到.*?表达式，然后再次使用非字母字符(第一个)，并继续操作。(这意味着，在这种情况下，我们可能会在[^a-zA-Z]和.*?中消耗该字符两次，但是如果引擎优化了自动机，则情况可能并非如此。

现在，lodo的构造表达式为:^(l|.*?(L|[^a-zA-Z]l))(o|.*?(O|[^a-zA-Z]o))(d|.*?(D|[^a-zA-Z]d))(o|.*?(O|[^a-zA-Z]o))。

我知道我的问题并未得到普及，但是我正在写出自己想出的解决方案，以备将来参考(即使只是针对我自己)。