Самый эффективный алгоритм для анализа и сравнения строковых ключей в Java - PullRequest
Новая
       49

Самый эффективный алгоритм для анализа и сравнения строковых ключей в Java

1 голос
/ 15 декабря 2011

У меня есть следующие Set<String> объекты. 

 "A_B_C_D_E_F_G",
 "A_B_C_D_E_X_G",
 "A_B_C_D_E_Z_G",
 "A_B_C_X_Y_F_G",
 "P_B_C_D_E_F_G",
 "A_C_N_D_E_F_G"
 ... and 10,000 more

Каждая строка представляет собой разделенный подчеркиванием список уникальных идентификаторов.Итак, чтобы помочь вам понять, вы можете думать о каждой строке следующим образом: 

 String[] uniqueIds = string.split("_");

Что я хочу сделать, это поместить каждую строку в Collection<String>, где строки сгруппированы, если отличается только один uniqueId,и различие возникает в том же «столбце».

Так что, если бы мы перебрали объекты Set<String> в примере, показанном выше, произошли бы следующие группировки 

Group1
 "A_B_C_D_E_F_G",
 "A_B_C_D_E_X_G", (because X is different than F)
 "A_B_C_D_E_Z_G", (because Z is different than F, and because Z and X are 
                   in the same column)

Group2
 "P_B_C_D_E_F_G", (because P is different than A, and is not the same column as 
                   in Group1)

Group3
 "A_B_C_X_Y_F_G", (because X is different than D, and is not the same column as 
                   in Group1 or Group2)
                  (because Y is different than E, and is not the same column as 
                   in Group1 or Group2)
Group4
 "A_C_N_D_E_F_G", (because C is different than B, and is not the same column as 
                   in Group1 or Group2 or Group 3)
                  (because N is different than C, and is not the same column as 
                   in Group1 or Group2 or Group 3)

Я пытаюсьвыяснить наиболее эффективный способ создания этих группировок.

Моим первоначальным предположением было бы начать с пустого Map<someKey,Collection<String>>.

Затем перебрать Set<String>, разбить каждую строку на массив uniqueId и пройти по карте в поисках * 1021.* который бы указывал, принадлежит ли эта строка в текущей коллекции или входит в новую коллекцию с другим someKey.Определение значения someKey может быть немного сложным ... может быть, это будет список номеров столбцов, разделенных подчеркиванием, значения которых изменились со времени первой строки?

Поскольку каждая строка содержит много символов uniqueIds, а размер Set<String> может составлять 10000. Казалось бы, этот алгоритм может работать медленно.

Есть предложения?

Спасибо!

ОБНОВЛЕНИЕ :::

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

Ответы [ 3 ]

1 голос
/ 15 декабря 2011

Создайте класс KeyComparator, который будет упорядочивать строковые массивы, игнорируя один элемент. Таким образом, new KeyComparator(0) будет игнорировать элемент 0, а [A, B, C] будет равно [D, B, C].

Разделите ваши ключи на массивы, как вы это сделали, и сохраните их в ArrayList<String[]>

Сортируйте этот массив N раз, где N - количество различных компонентов вашего ключа, используя компаратор (и изменяя пропущенный столбец от 0 до N-1).

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

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

A_B_C_D_E_F_G
B_B_C_D_E_F_G
B_C_C_D_E_F_G
1 голос
/ 16 декабря 2011

Сначала я клянусь алгоритмической абстракцией.

АБСТРАКЦИЯ

Эта группировка, конечно, только частичная упорядоченность, поэтому возможны разные решения. Предполагая, что каждый набор имеет одинаковое количество элементов: N.

Каждый набор имеет отношение к соседям (с одним отличным элементом) с (индексом) другого элемента.

Теперь у нас есть категории, несвязные группы, в которых (N - 1) элементов равны, а остальные изменяются. У нас также есть отдельные наборы, не подходящие для этих групп, и мы можем выбрать один из N элементов для изменения. Таким образом, они могут образовывать одну из N групп. Эти одиночные наборы не являются соседями, имеют как минимум 2 разных элемента.

Теперь для добавления нового набора к вашим оптимальным структурам данных необходимо сделать следующее: Проверьте, существует ли существующая категория (N возможностей).

Если найдено (регистр идентичен!), Добавьте его.

Если не найдено, отметьте отдельные наборы, чтобы сформировать группу из 2 наборов.

Если найден, удалите этот набор и введите новую категорию.

Если не найдено, добавьте набор в отдельные наборы.

РЕАЛИЗАЦИЯ

(Теперь, если количество элементов было ограничено, можно использовать битовые наборы; вы знаете, есть хорошие методы для подсчета количества различных битов; diff = a ^ b; boolean naybour = (diff & (diff - 1)) == 0;) 

class Singleset { N elements } // What is called set, named so to avoid nameclash with Set
class Subset { N-1 elements; equals, hashcode, Comparable }
class Differings { set of elements }
Map<Subset, Differings> categories; // Reconstitues full Singlesets
Map<Subset, Singleset> singlesets; // Every single set has N-1 subsets, every value has N-1 keys

Теперь Map можно сделать более умным с деревом на элементах. Итак, вы хотите: 

class MapSubsetTo<T> { ... }

Вы можете даже иметь одну карту для DifferingsOrSingleSet.

1 голос
/ 15 декабря 2011

Сначала я должен сказать, что я не эксперт по алгоритмам.Но, возможно, вам следует попробовать взглянуть на 1) Руководство по разработке алгоритмов Стивена Скиены - у него много решений для общей проблемы 2) Использование дерева, где буквы - это значения узлов.Возможно, вы могли бы как-то попробовать дерево суффиксов: http://en.wikipedia.org/wiki/Suffix_tree В статье говорится, что оно популярно для многих строковых операций.Если вы посмотрите на раздел «Приложения» в статье, он действительно кажется подходящим :) И он работает за линейное время.

Чтобы найти группу, к которой принадлежит строка, вы можете просто пройтись по деревуи посмотрите, до какой степени соответствует строка, а где нет.(Мое намерение)

...