regex O(n^2)时间复杂度a(n^2)

m0rkklqb  于 2022-12-27  发布在  其他
关注(0)|答案(3)|浏览(149)

给定:

sentence = "The world is a great place to live and eat"
dictionary = {
              "ea": "These words rym with each" ,
              "lace": "something"
             }

预期:

matched_words --> ["great", "place", "eat"]

我的方法:首先查找字典enries,然后检查字符串中的maches

Object.entries(dictionary).map(([key]) => {
        let regex = new RegExp(`[a-zA-Z]?${key}[a-zA-Z]?`, "g");
        let keywords = text.match(regex);
        return keywords
}

澄清:我注意到我的问题令人困惑。
我正在研究的是一些与阿拉伯语有关的东西。在阿拉伯语中,单词的定冠词"the"与单词相连。
示例:
"The peace"在英语中是两个单词,但在阿拉伯语中,定冠词"the"与这个单词相连,使它们成为一个单词,"The peace"==""
我想要的是把一些未使用的古代单词的定义放在弹出框中,比如Wikipedia

因此,我的方法是使用字典来保存古代单词及其定义,然后迭代字典键,将给定段落中的单词与给定关键字进行匹配,我使用regex忽略定冠词来匹配包含关键字的单词。

sentence = "السلام عليكم اصدقائي"  
dictionary = { "سلام" : "تعريف السلام"} 

output: ["السلام"]
gmxoilav

gmxoilav1#

我不太确定在指数级迭代增长或仅仅是多次迭代方法方面的幕后工作的细节。
但是,由于无论如何都必须使用一个动态构建的正则表达式/模式,我将joindictionarykeys数组转换为一个字符串,作为单个构建正则表达式的alternation,然后针对OP的text获得**match一次。
至于OP提供的示例,创建的正则表达式将是... /\b\w*(ea|lace)\w*/g

  • keys迭代一次
  • join也可以被计数为完整的迭代周期。
    • 摘要**

一切都可以归结为一个具有替换特性的正则表达式的执行效率。
因此,OP可能需要额外地进行性能测试,以确定在可能方法的不同实现中是否存在真正的瓶颈。

const dictionary = {
  ea: "These words rhyme with each" ,
  lace: "something"
};
const text = "The world is a great place to live and eat";

const dictAlternation = Object
  .keys(dictionary)
  .join('|');

console.log({
  dictAlternation,
  regex: RegExp(`\\b\\w*(${ dictAlternation })\\w*`, 'g'),
  matchingResults: text.match(
    RegExp(`\\b\\w*(${ dictAlternation })\\w*\\b`, 'g')
  )
});
.as-console-wrapper { min-height: 100%!important; top: 0; }
b09cbbtk

b09cbbtk2#

首先,代码没有产生预期的结果,如果您更正变量名并添加缺少的括号,它将输出:

[["reat", "eat"], ["place"]]

要得到想要的结果,你需要修改正则表达式,使它匹配 * 不止一个 * 周围的字母,并返回一个一维数组,使用flatMap

const text = "The world is a great place to live and eat";
const dictionary = {
    "ea": "These words rhyme with each" ,
    "lace": "something"
};

const results = Object.entries(dictionary).flatMap(([key]) => {
    let regex = new RegExp(`[a-zA-Z]*${key}[a-zA-Z]*`, "g");
    let keywords = text.match(regex);
    return keywords
});
console.log(results);

此算法仍有缺陷:它可以多次返回同一个单词。2当多个字典键出现在同一个单词中时,就会发生这种情况。3例如,如果文本中有单词“seapplace”,它就会出现两次。
如果是押韵的问题(“rym”?),那么你可能不想让元音跟在模式后面,也不想让元音直接出现在模式前面。不过,英语比这复杂得多,两个最后一个音节有“ea”的单词并不一定押韵(“棒极了”、“吃”、“近”、“熊”和“线性”这些词彼此不押韵)。但我会让你来定义,因为你的问题似乎不是关于押韵逻辑的。
您可以避免显式循环,而只依赖于一个正则表达式,从而将逻辑移到JavaScript引擎中的编译代码中:

const text = "The world is a great place to live and eat";
const dictionary = {
    "ea": "These words rhyme with each" ,
    "lace": "something"
};

const regex = RegExp(`\\b\\w*(?:${Object.keys(dictionary).join("|")})\\w*`, "gi");

const results = text.match(regex);
console.log(results);

请注意,此算法还确保即使文本中的一个单词可以与多个字典键匹配,它也只会出现一次。

watbbzwu

watbbzwu3#

在您的示例中,似乎只有字典键才是最重要的。如果是这样,那么它只是一个经过充分研究的问题,称为字符串搜索。如果性能真的那么重要,那么您可能必须研究这些算法之一,并找到一个库来执行它或自己实现它。
例如,您可以使用KMP:https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
对于每个模式,其性能为O([string的长度] + [pattern的长度]),或者总共为O([string的长度] * [# patterns] + [pattern的总长度])。

相关问题