최상의 압축을 제공하는 접두사 서브 스트링을 찾으십시오

StackOverflow https://stackoverflow.com/questions/150690

  •  02-07-2019
  •  | 
  •  

문제

문제:

문자열 목록이 주어지면, 일치하고 탈출 바이트로 대체되는 모든 문자열의 시작에서 빼면 가장 짧은 총 길이를 제공하는 하위 문자열을 찾으십시오.

예시:

"foo", "fool", "bar"

결과는 다음과 같습니다. 문자열이있는 기본 문자열로 "foo" "\0", "\0l", "bar" 및 총 길이는 9 바이트입니다. "\0" 탈출 바이트입니다. 원래 문자열의 길이의 합은 10 이므로이 경우 하나만 저장했습니다.

순진한 알고리즘은 다음과 같습니다.

for string in list
  for i = 1, i < length of string
      calculate total length based on prefix of string[0..i]
      if better than last best, save it
return the best prefix

그것은 우리에게 답을 줄 것이지만, 너무 비싼 O ((n*m)^2)와 같은 것입니다.

도움이 되었습니까?

해결책

접두사 나무의 숲 (trie)을 사용하십시오 ...

  f_2    b_1
 /       |
 o_2     a_1
 |       |
 o_2     r_1
 |
 l_1

그런 다음 최상의 결과를 찾아 최대화하여 보장 할 수 있습니다. (depth * frequency) 탈출 캐릭터로 대체됩니다. 분기를 수행하여 검색을 최적화하고 바운드 깊이를 먼저 검색하여 최대 값을 검색 할 수 있습니다.

복잡성 : O (c), 의견에 언급 된 바와 같이, 구축 및 최적을 찾기 위해서는 이에 따라 다릅니다. 첫 번째 요소 주파수 (O (a)-A가 알파벳 언어의 크기)를 주문하면 더 많은 분기를 잘라 내고 하위선 시간을 얻을 가능성이 높습니다.

나는 이것이 분명하다고 생각합니다. 나는 그것을 쓰지 않을 것입니다. 이것은 숙제 할당이 무엇입니까? ;)

다른 팁

목록을 정렬하여 시작하려고합니다. 그런 다음 첫 번째 문자를 다음 문자열의 첫 번째 문자와 비교하는 문자열에서 문자열로 이동합니다. 일단 성냥이 있으면 다음 숯을 보게됩니다. 지금까지 최상의 결과를 추적하는 방법을 고안해야합니다.

첫 번째 단계는 목록을 정렬하는 것입니다. 그런 다음 각 요소를 이전의 요소와 비교하여 가장 긴 2 자, 3 자, 4 자 등을 추적합니다. 그런 다음 그림은 15 개의 4 자 접두사보다 20 개의 3 자 접두사가 더 좋습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top