최소 빈도 문자가있는 문자열 찾기

Question

텍스트 파일이 3 개 있습니다. 텍스트의 세트로 하나는
(예. ABCDEAABBCCDDAABC)를 통해 검색 할
한 패턴의 숫자가 텍스트
(예. AB, EA, CC)
그리고 주파수를 포함하는 마지막에서 검색을 포함 각 문자의
(예.
4
B 4
C 4
3 D E
1
)
I가 알고리즘을 작성하려고하고 각 패턴에 대해 발생 빈도가 가장 낮은 문자를 찾고 해당 문자열을 검색 한 다음 주변 문자를 검사하여 문자열이 일치하는지 확인하십시오. 현재 나는 문자와 주파수를 각각 벡터로 가지고 있습니다. (각 벡터에 대한 i = 0은 각각 A 4가됩니다.)

더 빠른 데이터 구조일까요? 패턴 문자열을 조각과 비교하여 검사 할 수있는 효율적인 방법은 무엇입니까? 가장 빈번한 문자가 발견되면 텍스트 문자열?

Answer 1

인스턴스 수를 유지하고 검색된 총 문자 수에 따라 문자가 백분율보다 많이 나타나는지 확인하는 반복 루프를 실행할 수 있습니다 문자열의 총 길이입니다. 즉, 100 개의 문자와 5 개의 문자가있는 경우 100 개 문자 중 20 % 문자보다 큰 문자는 할인되어 해당 문자와 ​​일치하는 값을 전달하여 효율성을 높일 수 있습니다 ..

Answer 2

Aho-Corasick 알고리즘을 실행할 수 있습니다. 복잡성은 (전처리 후 - 그 복잡한 텍스트 무관 - 이루어진다)이다 Θ

• N 텍스트의 길이 (N + P),

• P는 일치의 갯수가

이것은 본질적으로 최적을 알 수있다.

1. 문자가 일치하지 않는 경우 알고리즘에 단위 시간이 걸립니다.

2. 문자가 일치 항목의 일부인 경우 일치 항목은 텍스트의 빈도와 관계없이 모든 문자를 포함합니다.