根据最长标记序列对项目列表进行分组

Question

我有一个项目列表，然后我想使用它们名称相同的部分将它们分类。因此，它需要将如下所示：

Foo Bar Apple
Foo Bar Banana
Foo Bar Carrot
Lorem Ipsum Car A 1 Hello
Lorem Ipsum Car A 2 Hello
Lorem Ipsum Car A 3 Hello
Lorem Ipsum Car A 4 Hello
Lorem Ipsum Car B 1 Hello
Lorem Ipsum Car B 2 Hello
Lorem Ipsum Car B 3 Hello
Lorem Ipsum Car B 4 Hello
Lorem Ipsum Car C 1 Hello
Lorem Ipsum Car C 2 Hello
Lorem Ipsum Car C 3 Hello
Lorem Ipsum Car C 4 Hello
This is a unique item

进入此：

- Foo Bar 
  - Apple
  - Banana
  - Carrot
- Lorem Ipsum Car A
  - 1 Hello
  - 2 Hello
  - 3 Hello
  - 4 Hello
- Lorem Ipsum Car B
  - 1 Hello
  - 2 Hello
  - 3 Hello
  - 4 Hello
- Lorem Ipsum Car C
  - 1 Hello
  - 2 Hello
  - 3 Hello
  - 4 Hello
- 
  - This is a unique item

我在尝试完成此任务时遇到了困难，这是到目前为止我最大的尝试之一（它不会产生我想要的输出）：

var arr = [
  { name: "Foo Bar Apple" },
  { name: "Foo Bar Banana" },
  { name: "Foo Bar Carrot" },
  { name: "Lorem Ipsum Car A 1 Hello" },
  { name: "Lorem Ipsum Car A 2 Hello" },
  { name: "Lorem Ipsum Car A 3 Hello" },
  { name: "Lorem Ipsum Car A 4 Hello" },
  { name: "Lorem Ipsum Car B 1 Hello" },
  { name: "Lorem Ipsum Car B 2 Hello" },
  { name: "Lorem Ipsum Car B 3 Hello" },
  { name: "Lorem Ipsum Car B 4 Hello" },
  { name: "Lorem Ipsum Car C 1 Hello" },
  { name: "Lorem Ipsum Car C 2 Hello" },
  { name: "Lorem Ipsum Car C 3 Hello" },
  { name: "Lorem Ipsum Car C 4 Hello" },
  { name: "This is a unique item" },
];

// Sort by name
arr.sort((a, b) => (a.name > b.name) ? 1 : -1);

var tree = {};

while (arr.length) {
    const firstItem = arr[0];
    const tokenizedA = firstItem.name.split(/\s+/);
    arr.splice(0, 1);
  
    previousLength = 0;
  
    for (let i = 0; i < arr.length; i++) {
      const otherItem = arr[i];
      const tokenizedB = otherItem.name.split(/\s+/);
  
      // find longest match sequence
      let matchedTokensCount = 0;
      for (let f = 0; f < Math.max(tokenizedA.length, tokenizedB.length); f++) {
        // if (tokenizedA[f].length < 4) break;
        if (tokenizedA[f] === tokenizedB[f]) matchedTokensCount++;
        else break;
      }
  
      const matchedTokens = tokenizedB.slice(0, matchedTokensCount).join(' ');
      const exclusiveTokens = tokenizedB.slice(matchedTokensCount).join(' ');
  
      if (matchedTokensCount) { //new category
        if (!tree[matchedTokens]) tree[matchedTokens] = [firstItem];
        tree[matchedTokens].push(otherItem);
        arr.splice(i, 1);
        i--;
        
        previousLength = matchedTokensCount;
      }
      else { // item doesnt match to previous category
        // tree[matchedTokens] = [firstItem, otherItem];
        break;
      }
  
    }
    //arr.splice(0, 1); // reduce the array
}
  

console.log(JSON.stringify(tree, 0, 4));

[我还尝试了另一种方法来创建带有项目的令牌树，但是当遍历只有一个孩子的扁平节点时，我无法遍历树并对其进行修改，因为在递归时还需要修改其密钥] >

var arr = [
  { name: "Foo Bar Apple" },
  { name: "Foo Bar Banana" },
  { name: "Foo Bar Carrot" },
  { name: "Lorem Ipsum Car A 1 Hello" },
  { name: "Lorem Ipsum Car A 2 Hello" },
  { name: "Lorem Ipsum Car A 3 Hello" },
  { name: "Lorem Ipsum Car A 4 Hello" },
  { name: "Lorem Ipsum Car B 1 Hello" },
  { name: "Lorem Ipsum Car B 2 Hello" },
  { name: "Lorem Ipsum Car B 3 Hello" },
  { name: "Lorem Ipsum Car B 4 Hello" },
  { name: "Lorem Ipsum Car C 1 Hello" },
  { name: "Lorem Ipsum Car C 2 Hello" },
  { name: "Lorem Ipsum Car C 3 Hello" },
  { name: "Lorem Ipsum Car C 4 Hello" },
  { name: "This is a unique item" },
];

// Sort by name
arr.sort((a, b) => (a.name > b.name ? 1 : -1));

var tree = {
  child: {}
};

for (let i = 0; i < arr.length; i++) {
  const item = arr[i];
  const tokens = item.name.split(/\s+/);

  let obj = tree;
  for (let f = 0; f < tokens.length; f++) {
    const t = tokens[f];
    if (!obj.child[t]) {
      obj.child[t] = {
        items: [],
        child: {}
      };
      obj = obj.child[t];
    } else {
      obj = obj.child[t];
    }
  }
  obj.items.push(item);
}

var traverse = function(o, fn) {
  for (var i in o.child) {
    fn.apply(this, [o, i, o.child[i]]);
    if (o.child[i].child) {
      traverse(o.child[i], fn, o);
    }
  }
};

traverse(tree, (obj, key, val, p) => {
     //console.log(key + ' ' + (val.items.length ? val.items[0] : undefined));
     if (val.items.length === 0) {
         if(obj.child) obj.child[key].empty = true;
     }
});

console.log(JSON.stringify(tree, 0, 4));

我有一个项目列表，然后我想使用它们名称相同的部分将它们分类。因此，它需要变成这样：Foo Bar苹果Foo Bar香蕉Foo Bar ...

Answer 1

您可以从两个字符串中获取公用部分，并将其用于分组。如果字符串不匹配，则采用下一个元素，而不是前一个元素。