세트에서 패턴 찾기

https://stackoverflow.com/questions/270541

06-07-2019
|

문제

문자열 세트에서 공통 문자를 결정하기 위해 어떤 알고리즘을 사용할 수 있습니까?

예제를 간단하게 만들기 위해, 나는 2+ 문자에 대해 연속으로, 샘플의 2 개 이상에 표시되는 경우에만 관심이 있습니다. 예를 들어:

0000ABCDE0000
0000ABCD00000
000ABC0000000
00ABC000DE000

알고 싶습니다 :

00은 1,2,3,4에 사용되었습니다
000은 1,2,3,4에 사용되었습니다
0000은 1,2,3에서 사용되었습니다
00000은 2,3에서 사용되었습니다
AB는 1,2,3,4에 사용되었다
ABC는 1,2,3,4에 사용되었다
ABCD는 1,2에서 사용되었다
BC는 1,2,3,4에 사용되었습니다
BCD는 1,2에서 사용되었다
CD는 1,2에서 사용되었다
DE는 1,4에서 사용되었습니다

해결책

나는 이것이 숙제가 아니라고 가정합니다. (만약 그렇다면, 당신은 당신의 자신의 회절주의입니다! ;-)

아래는 빠른 솔루션입니다. 시간 복잡성은입니다 O(m**2 * n) 어디 m 평균 문자열 길이입니다 n 문자열 배열의 크기입니다.

인스턴스 Occurrence 주어진 문자열이 포함 된 인덱스 세트를 유지합니다. 그만큼 commonOccurrences 일상적인 문자열 배열을 스캔하고 호출합니다 captureOccurrences 널이 아닌 문자열에 대해. 그만큼 captureOccurrences 루틴은 현재 색인을 An에 넣습니다 Occurrence 문자열의 가능한 하위 문자열에 대해 주어집니다. 드디어, commonOccurrences 그 결과 만 선택하여 결과를 형성합니다 Occurrences 적어도 두 개의 지수가 있습니다.

예제 데이터에는 질문에서 식별 한 것보다 훨씬 더 일반적인 하위 문자열이 있습니다. 예를 들어, "00ab" 각 입력 문자열에서 발생합니다. 내용 (예 : 모든 숫자, 모든 알파벳 등)을 기반으로 흥미로운 문자열을 선택하는 추가 필터는 독자의 운동으로 남겨진 것입니다. ;-)

빠르고 더러운 자바 소스 :

package com.stackoverflow.answers;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class CommonSubstringFinder {

    public static final int MINIMUM_SUBSTRING_LENGTH = 2;

    public static class Occurrence implements Comparable<Occurrence> {
        private final String value;
        private final Set<Integer> indices;
        public Occurrence(String value) {
            this.value = value == null ? "" : value;
            indices = new TreeSet<Integer>();
        }
        public String getValue() {
            return value;
        }
        public Set<Integer> getIndices() {
            return Collections.unmodifiableSet(indices);
        }
        public void occur(int index) {
            indices.add(index);
        }
        public String toString() {
            StringBuilder result = new StringBuilder();
            result.append('"').append(value).append('"');
            String separator = ": ";
            for (Integer i : indices) {
                result.append(separator).append(i);
                separator = ",";
            }
            return result.toString();
        }
        public int compareTo(Occurrence that) {
            return this.value.compareTo(that.value);
        }
    }

    public static Set<Occurrence> commonOccurrences(String[] strings) {
        Map<String,Occurrence> work = new HashMap<String,Occurrence>();
        if (strings != null) {
            int index = 0;
            for (String string : strings) {
                if (string != null) {
                    captureOccurrences(index, work, string);
                }
                ++index;
            }
        }
        Set<Occurrence> result = new TreeSet<Occurrence>();
        for (Occurrence occurrence : work.values()) {
            if (occurrence.indices.size() > 1) {
                result.add(occurrence);
            }
        }
        return result;
    }

    private static void captureOccurrences(int index, Map<String,Occurrence> work, String string) {
        final int maxLength = string.length();
        for (int i = 0; i < maxLength; ++i) {
            for (int j = i + MINIMUM_SUBSTRING_LENGTH; j < maxLength; ++j) {
                String partial = string.substring(i, j);
                Occurrence current = work.get(partial);
                if (current == null) {
                    current = new Occurrence(partial);
                    work.put(partial, current);
                }
                current.occur(index);
            }
        }
    }

    private static final String[] TEST_DATA = {
        "0000abcde0000",
        "0000abcd00000",
        "000abc0000000",
        "00abc000de000",
    };
    public static void main(String[] args) {
        Set<Occurrence> found = commonOccurrences(TEST_DATA);
        for (Occurrence occurrence : found) {
            System.out.println(occurrence);
        }
    }

}

샘플 출력 : (실제로 라인 당 하나의 발생 만 있었음에 유의하십시오. 블록 쿼트 마크 업이 선을 병합하는 것을 막을 수는 없습니다)

"00": 0,1,2,3 "000": 0,1,2,3
"0000": 0,1,2 "0000A": 0,1
"0000AB": 0,1 "0000ABC": 0,1
"0000ABCD": 0,1 "000A": 0,1,2
"000AB": 0,1,2 "000ABC": 0,1,2
"000ABCD": 0,1 "00A": 0,1,2,3
"00AB": 0,1,2,3 "00ABC": 0,1,2,3
"00ABC0": 2,3 "00ABC00": 2,3
"00ABC000": 2,3 "00ABCD": 0,1
"0A": 0,1,2,3 "0AB": 0,1,2,3
"0ABC": 0,1,2,3 "0ABC0": 2,3
"0ABC00": 2,3 "0ABC000": 2,3
"0ABCD": 0,1 "AB": 0,1,2,3 "ABC": 0,1,2,3 "ABC0": 2,3 "ABC00": 2,3
"ABC000": 2,3 "ABCD": 0,1 "BC": 0,1,2,3 "BC0": 2,3 "BC00": 2,3
"BC000": 2,3 "BCD": 0,1 "C0": 2,3 "C00": 2,3 "C000": 2,3 "CD": 0,1
"de": 0,3 "de0": 0,3 "de00": 0,3
"e0": 0,3 "e00": 0,3

다른 팁

이것은 아마도 아마도 NP- 하드 문제 일 것입니다. 그것은 비슷해 보입니다 다중 서열 정렬, 그것은. 기본적으로 다차원 적응할 수 있습니다 스미스-워터 맨 (= 로컬 시퀀스 정렬) 귀하의 요구에 대한. 그러나보다 효율적인 알고리즘이있을 수 있습니다.

나무를 통과하는 길이 문자 시퀀스 인 나무를 만듭니다. 각 노드에 문자열 참조가 통과시 추가되는 "세트"가 포함되어 있으면 (또는 계산을 유지). 그런 다음 N 위치를 추적하십시오.

이것은 작고 유한하고 밀도가 높은 알파벳으로 더 잘 작동합니다 (DNA는 내가 사용하는 첫 번째 장소였습니다).

편집하다: 당신이 관심있는 패턴을 미리 알고 있다면, 위의 내용은 나무를 미리 건축하여 작동하도록 변경 될 수 있습니다. 그런 다음 트리를 확장하지 않고 트리에 있는지 확인하기 만하면됩니다.

예

입력

abc
abd
abde
acc
bde

나무

a : 4
  b : 3
    c : 1
    d : 2
      e : 1
  c : 1
    c : 1
b : 4
  d : 3
    e : 2
  c : 1
c : 3
  c : 1
d : 3
  e : 2

웹에서 "접미사 나무"를 찾아보십시오. 또는 Dan Gusfield의 "현, 나무 및 시퀀스에 대한 알고리즘"을 픽업하십시오. 확인할 책이 없지만 접미사 나무의 Wikipedia 페이지 205 페이지에는 문제에 대한 솔루션이 포함되어 있다고 말합니다.

미리 검색 해야하는 "값"을 알고 있습니까? 아니면 문자열을 구문 분석하고 게시 한 것처럼 통계를 제공하려면 코드가 필요합니까?

Boyer-Moore 알고리즘을 사용하는 것은 미리 찾고있는 것을 알고 있다면 하위 문자열이 존재하는지 (그리고 심지어 찾을 수 있는지)를 알 수있는 매우 빠른 방법입니다.

거리 매트릭스 분석을 사용할 수 있습니다. 모든 대각선 이동 (비용 변경 없음)은 정확히 일치합니다.

당신은 찾을 수 있습니다 접미사 배열 데이터의 일반적인 하위 문자열이 얼마나 빈번한 지에 따라 접미사 트리보다 단순하고 효율적입니다. 충분히 일반적인 경우보다 정교한 접미사 건설 알고리즘이 필요합니다. (순진한 방법은 라이브러리 정렬 기능을 사용하는 것입니다.)

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow