Групповые строки по самой длинной общей стартовой подстроке

Question

В этом проблема. Скажем, у меня есть эти строки:

• Apple Ipad мини 32gb
• Apple Ipad мини 64gb
• Apple Ipad воздуха 64gb
• Apple Ipad воздуха 32gb
• Panasonic GH4
• Самсунга s2 галактики
• samsung s2 галактика красный
• samsung s3 галактика

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

• Apple Ipad мини: [Apple Ipad мини 32gb, Apple Ipad мини 64GB]
• Apple Ipad воздуха: [Apple Ipad воздуха 64GB, яблоко Ipad 32gb]
• GH4 Panasonic: [Panasonic GH4]
• Samsung s2 галактики: [Samsung s2 галактики, Samsung s2 галактики красный]
• Samsung s3 галактики

Суть заключается в том, чтобы отделить имя элемента от его атрибутов (цвет, объем памяти и т. Д.).

Я использовал этот алгоритм для нахождения наибольшего общей подстроки: link

Может ли вы, ребята, поделиться своими идеями? Никакого кода или реализации не требуется. Спасибо.

Отредактировано:

this.data = _.sortBy(this.data, function(item) { 
     return item.title; 
    }); 

    var i = 0; 
    var groups = {}; 
    var len = this.data.length - 1; 
    while(i < len) { 
     var key = this.lcs(this.data[i][this.attr], this.data[i+1][this.attr]) || this.data[i][this.attr]; 
     groups[key] = true; 
     i++; 
     while(this.data[i][this.attr].startsWith(key) && i < len) { 
      i++; 
     } 
    } 
    console.log(groups) 

Это отлично работает (проверено только при добавлении ключа). Но я хочу добавить галактику samsung s3 в список тоже. Спасибо за помощь, ребята!

Answer 1

Если вы просто хотите просто сгруппировать длинный общий префикс (это означает, что «apple ipad mini» будет выбран, хотя «apple ipad» даст большую группу), может быть, что-то вроде этого?

sort the list 
i = 0 
while i < end of list: 
    key = longest common prefix of list[i] & list[i + 1] 
     or list[i] if the common prefix is less than (1?) words or i is the last index 
    groups[key] = list[i++] 
    while key is prefix of list[i]: 
    add list[i++] to groups[key] 

Answer 2

Попытка решить проблему с сравнения двух строк с одинаковыми словами и взглядом вверх, если длина слов меньше, чем предыдущий путь.

function groupObject(i, l) { 
 
    return { item: i, length: l }; 
 
} 
 

 
function group(r, a, i, o) { 
 
    var rr = r.item.split(' '), 
 
     aa = a.split(' '), 
 
     j = 0, 
 
     key, keys = []; 
 

 
    while (aa[j] === rr[j]) { 
 
     keys.push(aa[j]); 
 
     j++; 
 
    } 
 
    if (keys.length < r.length && i < o.length - 1) { 
 
     return group(groupObject(o[i + 1], 0), a, Number.MAX_VALUE, o); 
 
    } 
 
    key = keys.join(' '); 
 
    if (!key || keys.length < r.length && i === o.length - 1) { 
 
     key = a; 
 
    } 
 
    grouped[key] = grouped[key] || []; 
 
    grouped[key].push(a); 
 
    return groupObject(a, keys.length); 
 
} 
 

 
var data = ['apple ipad mini 32gb', 'apple ipad mini 64gb', 'apple ipad air 64gb', 'apple ipad air 32gb', 'panasonic gh4', 'samsung s2 galaxy', 'samsung s2 galaxy red', 'samsung s3 galaxy'], 
 
    grouped = {}; 
 

 
data.reduce(group, groupObject(data[1], 0)); 
 
document.write('<pre>' + JSON.stringify(grouped, 0, 4) + '</pre>');