我有大量的字符串,我知道它们是由一组有限的模式构建的,但我不知道是哪些。我需要在一个非常大的数据集上相当快地计算这些模式。
例如,这组模板(我不知道):
"Hello, my {0} is: {1}"
"{0} has left our team."
"{0} has joined the team {1}!"
匹配下面的一组行,我唯一的:
Hello, my name is: Slim Shady
Mike has left our team.
Mike has joined the team Liquid!
Hello, my name is Nikole
Nick has joined the team Spirit!
Elizabeth has left our team.
任务:查找相似字符串中的模式。也就是说,在文本中找到允许您自动提出此类模式的模式。可以有很多行。
到目前为止,我已经提出了使用 N-gram 的编辑距离之类的方法。
但这东西的范围比我需要的要广,运行时间的重要性不亚于寻找模式的准确性。
因为我的单词可以完全匹配且没有错误,在我看来,在这里你可以通过某种方式提高性能。
我想制作一个单词的字母表,而不是字母,这样就可以通过单词来搜索句子。
UPD:以防万一,我会澄清在编译时既没有模板也没有字符串本身。字符串作为输入提供给程序,没有人会给我们模板。
UPD2:我们需要在已经通过的行中实时查找模式,以便在接下来我们可以找到它们的匹配项。
(评论)假设我们有
nofferМама наша мыла раму和mofferМама мыла мою раму。它必须是一个模板Мама {0} мыла {1} раму或两个模板:Мама {0} мыла раму,Мама мыла {0} раму? 这样的例子还有很多。为了避免这样的歧义,要么你需要更清楚地了解你有什么样的任务,要么你需要指出一个具体的含义,这样你才能找到一个独特的解决方案。
模式应尽可能通用,即 Мама {0} мыла {1} раму. 但它适用于类似的线路。不只是一种模式{0}
(评论)问题来了,为什么不使用模式
{0}?这是最一般的。问题似乎是需要在模板集上引入某种顺序。一般来说,这个顺序是非线性的。它需要以某种方式线性化。这似乎是一项艰巨的任务。如果你说你为什么需要这个任务,你可以考虑一下。
这是整个任务: D 我需要找到这些线条的模式,以便将高度相似的线条组合成模式,例如,您可以采用标准形式的相似度百分比。
UPD3:模板应该连接相似的字符串。类似的字符串将被视为匹配的字符串N%。