자바에서 문자열 키를 구문 분석하고 비교하는 가장 효율적인 알고리즘

Question

다음과 같은 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 

각 문자열은 밑줄로 구분 된 고유 ID 목록입니다. 하나가 UniqueID가 다르고, 경우

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

은 내가 문자열이 함께 그룹화되어 Collection<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) 

발생할 수있는 다음과 같은 그룹 위의 예에서 Set<String> 개체를 통해 루프.

처음에는 내 생각 엔 빈 Map<someKey,Collection<String>>으로 시작할 것입니다.

그런 다음 Set<String>을 통해 루프는 UNIQUEID 배열에 각 문자열을 분할하고 해당 문자열이 현재 컬렉션에 속하거나 다른 someKey으로 새 컬렉션에 들어가는 경우 말할 것 것 someKey를 찾기 위해지도를 통해 이동합니다. 무엇 someKey 정의는 조금 까다 롭습니다 ... 어쩌면 그것은 첫 번째 문자열 이후 변경된 값을 가진 열 번호의 밑줄로 구분 된 목록일까요?

각 문자열에는 uniqueIds이 많이 포함되어 있고 Set<String> 크기는 10,000 일 수 있으므로이 알고리즘은 느리게 진행될 수 있습니다.

제안 사항?

감사합니다.

UPDATE :::

이 문자열은 1 개 이상의 그룹에 들어갈 수있는 경우가 있습니다. 그렇다면 기준을 충족하는 첫 번째 가용 그룹에 배치됩니다.

Answer 1

먼저 알고리즘 전문가가 아닙니다. 하지만 아마도 을 살펴보아야 할 것입니다. 1) Steven Skiena의 알고리즘 설계 매뉴얼 - 그는 공통적 인 문제에 대한 많은 해결책을 가지고 있습니다. 2) 문자를 노드 값으로 사용하는 트리 사용. 어쩌면 당신은 어쨌든 접미어 트리를 시도 할 수 있습니다 : http://en.wikipedia.org/wiki/Suffix_tree이 기사는 많은 문자열 작업에 널리 사용된다고 말합니다. 기사의 "응용 프로그램"섹션을 살펴보면 정말 맞는 것 같습니다. 그리고 그것은 선형 시간으로 실행됩니다.

문자열이 속한 그룹을 찾으려면 트리를 따라 걸으며 문자열이 어느 정도 일치하는지 그리고 그렇지 않은지 찾아보십시오.

Answer 2

하나의 요소를 무시하고 문자열 배열을 정렬하는 클래스 KeyComparator을 만듭니다. 따라서 new KeyComparator(0)은 요소 0을 무시하고 [A, B, C]는 [D, B, C]와 같습니다.N이 키에 고유 한 구성 요소의 수는 비교기를 사용하여 (그리고 다양한이며, N 시간을 당신이 한대로 배열로 키를 분할 및 ArrayList<String[]>

정렬이 배열을 저장할

, 0에서 N-1까지의 생략 된 열).

각 정렬 후에는 함께 정렬 된 값 (그리고 비교자를 사용하여 동일 함)을 그룹화해야합니다.

그러나 다음과 같이하면 어떻게됩니까? 첫 번째 열을 기준으로 처음 두 그룹을 그룹화하지만 두 번째 열을 사용하여 마지막 두 그룹을 그룹화합니다.

A_B_C_D_E_F_G 
B_B_C_D_E_F_G 
B_C_C_D_E_F_G 

Answer 3

나는 알고리즘 추상화를 먼저 맹세합니다.

추상화

이 그룹은 이렇게 서로 다른 솔루션이 가능 물론 단지 부분적인 순서입니다. N.

모든 세트와 이웃 (다른 하나 개의 원소를 갖는) (인덱스)가 다른 요소의 관계를 갖는다 : 모든 세트를 가정 는 같은 수의 요소를 갖는다.

이제는 (N - 1) 개의 요소가 같고 나머지는 다양하게 나오는 분리 된 그룹이 있습니다. 우리는 또한 그 그룹에 속하지 않는 단일 세트를 가지며 다양하게 N 개의 요소 중 하나를 선택할 수 있습니다. 그래서 그들은 N 그룹 중 하나를 형성 할 것입니다. 이 단일 세트는 이웃이 아니며 최소한 두 가지 요소가 있습니다.

이제 최적의 데이터 구조에 새 세트를 추가하려면 다음을 수행해야합니다. 기존 카테고리가 있는지 확인하십시오 (N 가능성).

발견되면 (동일한 경우!) 추가하십시오.

찾을 수없는 경우 단일 세트를 검사하여 2 세트의 그룹을 구성하십시오.

발견되면 해당 세트를 제거하고 새로운 카테고리를 소개합니다.

찾을 수없는 경우 세트를 단일 세트에 추가하십시오.

이행

(요소의 수를 제한한다면 이제, 하나는 BitSets를 사용할 수 있습니다, 당신은 다른 비트의 수를 계산하는 좋은 기술이있다, 알고 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 

지금 지도 < 하위 집합, ...> 요소의 트리를 사용하여 더 영리하게 수행 할 수 있습니다. 원하는 위치 :

class MapSubsetTo<T> { ... } 

지도를 DifferingsOrSingleSet으로 만들 수도 있습니다.