javascript 从一组字符串/文本中提取通配符字符串(仅 * 星号)?

zpgglvta  于 2023-06-04  发布在  Java
关注(0)|答案(3)|浏览(352)

bounty还有2天到期。此问题的答案有资格获得+50声望奖励。Savaratkar正在寻找一个答案从一个有信誉的来源

是否有算法或代码/lib(*NodeJS首选 *),从一组字符串或文本中提取通配符字符串。
例如,以下是作为输入的字符串集合(*forgive my英语 *):

apple pie is not too so good
apple pie is not so good
apple pie is too good

我将能够提取一个通配符字符串只有星号 *,像这样:

apple pie is * good

通配符中还有其他特殊字符,但我只想使用 * 星号。
在某种程度上,我们可以说我需要从输入字符串中提取正则表达式。现在有没有一个库或算法来实现这一点?
请让我知道如果需要更多的信息。

mf98qq94

mf98qq941#

我假设您希望提取一个通配符,它将适用于所有字符串。如果没有,我不知道如何开始。
另外,在第一遍中,我将纠正您的英语,将"apple pie is not too so good"更改为"apple pie is not very good"。原因将在下面清楚。
为了解决这个问题,我们可以将其分解为找到所有字符串的公共前缀,以及所有字符串的公共后缀,并使用*通配符将它们连接在一起。它可能看起来像这样:

const reverse = (s) => [...s] .reverse () .join ('')

const commonPrefix = ([first, ...rest]) =>
  first .slice (0, [... first] .findIndex ((c, i) => rest .some (s => s .at (i) !== c)))

const commonSuffix = (ss) =>
  reverse (commonPrefix (ss .map (reverse)))

const extractWildcard = (str) => 
  commonPrefix (str) + '*' + commonSuffix (str)

console .log (extractWildcard ([
  'apple pie is not very good', 
  'apple pie is not so good', 
  'apple pie is too good'
])) //=> 'apple pie is * good'

我们的commonPrefix函数找到某个字符串与第一个字符串不同的第一个索引,然后将字符串切片到该点。commonSuffix使用字符串reverse辅助函数,反转所有字符串,找到它们的公共前缀并反转该值。(还有很多其他的方法可以做到这一点,其中一些更有效,但它们涉及到计算最长的字符串开始,并且都更复杂。如果这里有性能问题,我会考虑使用其中一个。)
但是这里有一个问题,通过使用原始的"apple pie is not too so good"可以看出:

extractWildcard ([
  'apple pie is not too so good', 
  'apple pie is not so good', 
  'apple pie is too good'
]) //=> "apple pie is *o good"

通配符旁边的额外o是不需要的。为了解决这个问题,我们可以创建一个更复杂的extractWildcard版本来处理空格:

const extractWildcard2 = (s, pre = commonPrefix (s), suf = commonSuffix (s)) => 
   pre .slice (0, pre .lastIndexOf (' ')) + ' * ' + suf .slice (suf .lastIndexOf (' ') + 1)

extractWildcard2 ([
  'apple pie is not too so good', 
  'apple pie is not so good', 
  'apple pie is too good'
]) //=> "apple pie is * good"

更新

下面是一个更高效的commonSuffix版本:

const commonSuffix = (ss, length = Math .max (...ss .map (s => s .length))) =>
  (ss [0] || '') .slice (length - Array .from ({length}, (_, i) => i + 1) .findIndex (
    (i) => console .log ({i}) || ss .some (s => s .at (-i) !== ss [0] .at (-i))
  ))

我会坚持使用更简单的方法,除非这被证明是应用程序中的实际瓶颈。

更新二:简单性

(This不是关于实际问题,而是关于代码简单性的讨论;请随意忽略它。)
一条评论说:
即使对我来说,这也是一段几乎不可读的代码[...]。对于公共前缀确实存在更简单、更可读的算法。
我想就这一点进行辩论。Rich Hickey有一个著名的演讲,Simple Made Easy,它区分了“简单”和“容易”。* 简单 * 是一个相当客观的衡量标准,衡量的是有多少概念被缠绕在一起来提供一个解决方案。* 容易 * 是一个主观的衡量标准,衡量解决方案对特定人员的熟悉程度。
通过编写声明性代码,通过避免像可变状态这样的技术,通过使用表达式而不是语句,以及通过避免变量赋值的时间效应,我认为这段代码相当简单。它可能不熟悉,因此对某些用户来说可能不那么容易。
上面的代码是我写的;我没有从某个地方开始,把它削减到最低限度。但我们可以试试。我们可以从最命令式的--也是最熟悉的--代码风格开始:

const commonPrefix = (strings) => {
  const firstString = strings [0];
  const first = firstString .split ('');
  const rest = strings .slice (1);
  let index = -1;
  let indexFound = false;
  for (let i = 0; i < first .length; i ++) {
    const character = first [i];
    for (let j = 0; j < rest .length; j ++) {
       const testString = rest [j];
       const testCharacter = testString [i]
       if (testCharacter !== character) {
         index = i;
         indexFound = true;
         break;
       }
    }
    if (indexFound) {
      break;
    }
  }
  const characters = first .slice (0, index); 
  const result = characters .join ('');
  return result;
}

这可能对一些人来说更 * 熟悉 / 容易 *。但让我们看看实现。我们有12个局部变量。我们使用一对嵌套循环,每个循环包含一个if语句。在某些情况下,我们在两个循环中执行早期转义。
如果我们稍微做一点清理,并认识到外部循环只是在做Array.prototype.findIndex已经为我们做的工作,那么我们可以写一个我认为更简单的版本:

const commonPrefix = (strings) => {
  const firstString = strings [0]
  const first = firstString .split ('')
  const rest = strings .slice (1)
  const index = first .findIndex ((c, i) => {
    for (let j = 0; j < rest .length; j ++) {
       const testString = rest [j]
       if (testString [i] !== c) {
         return true
       }
    }
    return false
  })
  return first .slice (0, index) .join ('')
}

我们还删除了一些局部变量:testCharactercharactersresult,而不会损害可读性。
同样,我们应该能够注意到剩余的循环正在执行与Array.prototype.some相同的工作。我们可以清理一下然后离开:

const commonPrefix = (strings) => {
  const first = strings [0] .split ('')
  const rest = strings .slice (1)
  const index = first .findIndex ((c, i) => rest .some (s => s .at (i) !== c))
  return first .slice (0, index) .join ('')
}

我们现在正在接近我认为的一个简单函数。但是我们可以注意到index在一行中定义,并且只在下一行中使用一次,因此如果我们选择,我们可以简单地将其折叠起来,并删除局部变量。同样,参数strings仅用于定义firstrest;我们可以通过参数解构来实现相同的目的,并跳过这些定义。在这一点上,我们回到我的初始版本:

const commonPrefix = ([first, ...rest]) =>
  first .slice (0, [... first] .findIndex ((c, i) => rest .some (s => s .at (i) !== c)))

请注意,此版本不使用first .split (''),而是使用[... first]。两者都行;两者看起来都很简单。这段代码使用s .at (i)而不是s [i],因为早期版本有一个并行的commonSuffix,而at更容易使用。但我们可以改变这一点两个选择都可以
总之,这段代码比最长的版本简单得多。重要的不是长度本身。但是简单代码的一个常见副作用是代码更短。

nvbavucw

nvbavucw2#

我假设输入的单词被认为是原子的,不应该被分解。否则,示例输入的解决方案可以在输出中保留更多的原始字符:

apple pie is *o*o good

然后,我还将假设这些单词由空格而不是其他字符分隔,因此第一步是将输入短语拆分为以单词为元素的数组。

问题结构

你可以把这看作是一个图形问题,其中节点是已经从每个短语中处理的单词的组合状态,或者以其他方式放置:这些短语中的当前词索引的元组。边是有向的和加权的,并且表示从一个状态进展到另一个状态的“成本”。成本包括通配符使用的每个单词的点数。如果有多个解决方案具有相同的成本,则首选通配符较少的解决方案。因此,我们可以为引入的每个通配符计算0.5的成本。
例如:如果输入中的单词都不同,则解决方案是“*”,并且该解决方案的成本是单词的总计数加上单个通配符的0.5。
另一个例子是所有输入短语完全相同,比如4次“这是一个短语”,因此该短语也将是输出。该解决方案的成本为0,因为使用通配符没有省略任何单词。

最佳搜索算法

然后在该图上执行Dijkstra算法以找到解,即结束状态,其中所有单词索引都在其相应短语的末尾。
我们可以通过关注那些不需要两个连续通配符的搜索路径来消除一些搜索路径。因此,我们应该以这样一种方式递增索引,即在使用通配符之后,更新后的索引引用的单词都是相同的。如果我们决定直接使用短语的当前单词(而不是通配符),我们应该在其他字符串中找到相同的单词(从它们的当前索引开始)。为了科普这是不可能的,或者仍然导致高成本,我们还应该考虑使用通配符跳过所有当前单词(所有索引递增1)的场景。

优先级队列

由于JavaScript没有本机优先级队列,我重用了this answer的堆实现。

实现

下面是上述算法的实现:

// From https://stackoverflow.com/a/66511107/5459839
const MinHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]>h[j+1][0])j++;if(j>=h.length||k<=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k<h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};

function commonPatternFor(strings) {
    const makeKey = JSON.stringify;
    // When there is a tie in the number of removed words, the number of wildcards is minimised:
    const WILDCARD_COST = 0.5; 
    
    // Words are considered atomic:
    const phrases = strings.map(s => s.split(" "));
    // The end state to achieve:
    const end = phrases.map(s => s.length);
    // Heap has entries with [cost, current indexes, previous indexes, isLastStepWildCard]  
    const heap = [ [0, phrases.map(() => 0), null, WILDCARD_COST] ];
    // Register the optimal paths as linked list
    const comeFrom = new Map;
    
    
    while (true) { // Best-first Loop
        // Extract best state so far
        let [cost, curr, prev, wildcardCost] = MinHeap.pop(heap);
        const currKey = makeKey(curr);
        if (comeFrom.has(currKey)) continue; // Already visited this state
        comeFrom.set(currKey, prev);

        if (phrases.some((words, i) => curr[i] === words.length)) {
            // Some phrases have been fully accounted for. Count number of remaining words:
            const diff = phrases.reduce((acc, words, i) => acc + words.length - curr[i], 0);
            if (!diff) { // BINGO!
                // unwind solution
                const sol = [];
                while (true) {
                    const prev = comeFrom.get(makeKey(curr));
                    if (!prev) return sol.reverse().flat().join(" ");
                    const sliceArr = phrases[0].slice(prev[0], curr[0]);
                    const slice = sliceArr.join(" ");
                    if (phrases.every((words, i) => words.slice(prev[i], curr[i]).join(" ") === slice)) {
                        sol.push(sliceArr);
                    } else if (sol.at(-1) != "*") {
                        sol.push("*");
                    }
                    curr = prev;
                }
            }
            // As some phrases have no more remaining words, we use a single wildcard for
            //    covering the remaining words in the other phrases
            MinHeap.push(heap, [cost + diff + wildcardCost, end, curr, 0]); 
        } else {
            // See if there are common words in all phrases starting at their current positions
            let k = 0;
            while (true) {
                const word = phrases[0][curr[0]+k];
                if (word === undefined || !phrases.every((words, i) => words[curr[i]+k] === word)) break;
                k++;
            }
            if (k) { // Yes, all phrases have k common words starting at their current positions
                MinHeap.push(heap, [cost, curr.map(i => i + k), curr, WILDCARD_COST]); 
                // Also consider alternative scenarios where we introduce a wildcard
                phrases.forEach((words, i) => {
                    const k = words.indexOf(words[curr[i]], curr[i] + 1);
                    if (k < 0) return;
                    const diff = k - curr[i];
                    const next = [...curr];
                    next[i] = k;
                    MinHeap.push(heap, [cost + diff + wildcardCost, next, curr, 0]); 
                });
            } else { // Not all current words are the same: we must use a wildcard
                phrases.forEach((words, i) => {
                    const word = words[curr[i]]; // Try to find this word in the other phrases
                    let diff = 0;
                    const next = phrases.map((words2, j) => {
                        let k = words2.indexOf(word, curr[j]);
                        diff += k - curr[j];
                        return k;
                    });
                    if (!next.includes(-1) && diff) {
                        MinHeap.push(heap, [cost + diff + wildcardCost, next, curr, 0]); 
                    }
                });
                // Also consider the scenario where a wildcard is used to cover for ALL current words
                MinHeap.push(heap, [cost + phrases.length + wildcardCost, curr.map(i => i + 1), curr, 0]); 
            }
        }
    }
}

const tests = [
    [
        "apple pie is not very good", 
        "apple pie is not so good", 
        "apple pie is too good"
    ], [
        "apple pie is not very good and for me that is fine", 
        "the apple pie is not as good as they told me", 
        "apple pie is too good for me and you"
    ], [
        "this is such a very common old phrase this is a common phrase", 
        "this is a common phrase while this is not common", 
        "this is a common phrase",
    ], [
        "a b c d e f g h",
        "i j k l m n o p",
        "q r s t u v w x",
        "y z a b c d e f",
        "g h i j k l m n",
        "o p q r s t u v",
        "w x y z a b c d",
    ], [
        "a a a b a a b b a a b a",
        "a a a a a b a b a a b b",
        "a a b a a a b a b a a b"
    ]
];

for (const test of tests) {
    const sol = commonPatternFor(test);
    console.log(sol);
}

这个算法没有一个好的最坏情况下的时间复杂度,所以如果你给它更多更长的短语,有很多常见的单词,它会变得太慢。

4c8rllxm

4c8rllxm3#

你可以使用正则表达式来实现这一点。通过将*替换为(.*?),从输入中构建正则表达式。你需要escape the special characters

let search = "apple pie is * good";
let pattern = search
  .replace(/[\-\[\]{}()+?.,\\\^$|#\s]/g, "\\$&")
  .replace(/\*/g, "(.*?)");
let regexp = new RegExp(pattern, "gs");
let matches = `apple pie is not too so good
apple pie is not so good
apple pie is too good
something else`.match(regexp);
console.log(matches);

相关问题