Сгруппируйте список предметов на основе самой длинной последовательности токенов

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

Я с трудом пытаюсь выполнить sh эту задачу, это одна из моих лучших попыток (которые не дают желаемого результата):

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));

Answer 1

Вы можете получить общую часть из двух строк и использовать ее для группировки. Если строка не совпадает, вместо предыдущего элемента берется следующий элемент.

function getCommon(a, b) {
    var i = -1,
        l = Math.min(a.length, b.length);

    while (i++ < l) if (a[i] !== b[i]) break;
    return a.slice(0, i);
}

var data = ['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'],
    i,
    common,
    result = [];

for (i = 0; i < data.length; i++) {
    if (common === getCommon(data[i - 1] || '', data[i])) {
        result[result.length - 1].push(data[i].slice(common.length));
        continue;
    }
    common = getCommon(data[i] || '', data[i + 1] || '');
    result.push([common, data[i].slice(common.length)]);
}

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }