문자열에서 중복된 문구를 찾기 위해 어떤 알고리즘을 사용할 수 있나요?

Question

임의의 문자열이 주어지면 중복된 문구를 찾는 효율적인 방법은 무엇입니까?문구가 포함되려면 특정 길이보다 길어야 한다고 말할 수 있습니다.

이상적으로는 각 문구의 발생 횟수로 끝나는 것입니다.

Answer 1

이전 사람들이 언급했듯이 접미사 트리는 작업에 가장 적합한 도구입니다.접미사 트리에 대해 내가 가장 좋아하는 사이트는 다음과 같습니다. http://www.allisons.org/ll/AlgDS/Tree/Suffix/.한 페이지에 접미사 트리의 모든 유용한 용도를 나열하고 테스트를 수행합니다. js 문자열을 테스트하고 예제를 통해 작업할 수 있는 애플리케이션이 내장되어 있습니다.

Answer 2

이론에 의하면

• ㅏ 접미사 배열 중복된 하위 문자열을 감지하기 위해 선형 공간과 시간을 사용하도록 구현할 수 있으므로 '가장 좋은' 답변입니다.그러나 순진한 구현은 실제로 접미사를 정렬하는 데 O(n^2 log n) 시간이 걸리며 이를 읽을 수는 있지만 O(n)은 물론이고 O(n log n)로 줄이는 방법도 완전히 명확하지 않습니다. 원한다면 관련 서류.
• ㅏ 접미사 트리 접미사 배열보다 약간 더 많은 메모리를 사용할 수 있지만(여전히 선형적임) 트리에 항목을 추가할 때 기수 정렬 아이디어와 같은 것을 사용할 수 있으므로 빠르게 구축하기 위해 구현하기가 더 쉽습니다(이름의 Wikipedia 링크 참조). 세부).
• 그만큼 KMP 알고리즘 또한 알아두면 좋은 점은 긴 문자열 내에서 특정 하위 문자열을 매우 빠르게 검색하는 데 특화된 것입니다.이 특별한 경우만 필요한 경우 KMP를 사용하면 충분 색인을 먼저 구축할 필요가 없습니다.

실제로

나는 당신이 실제 자연어 문서(예:영어) 단어, 그리고 실제로 수집한 데이터로 뭔가를 하고 싶어합니다.

이 경우에는 빠른 작업을 수행하고 싶을 수도 있습니다. n-그램 n=2 또는 3과 같은 일부 작은 n에 대한 분석입니다.예를 들어 구두점, 대문자 사용 및 단어 형태소 분석(실행, 둘 다 실행 -> '실행')을 제거하여 문서를 단어 목록으로 토큰화하여 의미론적 일치를 높일 수 있습니다.그런 다음 지금까지의 발생 횟수에 따라 인접한 각 단어 쌍의 해시 맵(예: C++의 hash_map, Python의 사전 등)을 구축합니다.결국에는 코딩 속도가 매우 빠르고 실행 속도도 그리 느리지 않은 매우 유용한 데이터를 얻게 됩니다.

Answer 3

접미사 트리 이것을 구현하는 좋은 방법입니다.해당 기사의 하단에는 다양한 언어로 구현된 링크가 있습니다.

Answer 4

jmah가 말했듯이 이를 위해 접미사 트리/접미사 배열을 사용할 수 있습니다.

사용할 수 있는 알고리즘에 대한 설명이 있습니다. 여기 (섹션 3.1 참조)

그들이 인용한 책(Gusfield, 1997)에서 더 자세한 설명을 찾을 수 있습니다. 구글 도서에서.

Answer 5

n개의 항목(i=1,2,3,...,n)을 포함하는 정렬된 배열 A가 있다고 가정합니다.

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

이 알고리즘은 O(n) 시간에 실행됩니다.