접미사 검색 시간

Question

누구든지 아래 진술에 대한 이유를 알고 있습니까? 또는이 유형의 질문을하는 더 나은 웹 사이트가 있습니까? 모든 포인터를 주시면 감사하겠습니다.

패턴이 길이가 n 인 텍스트 (길이가 n 인 경우)에서 발생하는 경우 해당 텍스트의 접미사 트리에서 모든 k 회에 대한 패턴 검색은 O (n + k)의 비용이 부과됩니다.

Answer 1

접미어 트리 검색에 걸리는 시간은 검색하는 패턴의 길이에 비례합니다. 미시시피에 대한 접미사 트리를 만들고 SSI를 검색했다면 수행해야하는 조회는 3 일 것입니다. 시간은 O (n)입니다. 여기서 n은 패턴의 길이입니다.

Answer 2

이 진술을 어디서 발견했는지에 따라 상황에 맞는 구체적인 이유가있을 수 있습니다.

그러나 '+ k'의 일반적인 이유는 사용자에게 반환 된 결과 목록에서 찾은 각각의 일치 항목을 삽입하기 위해 O (k) 추가 작업이 필요하다는 것입니다. 접미어 트리 대신에 반전 된 파일이 사용 된 경우는 반드시 필요하지 않습니다. 인덱스 에있는 반전 된 목록 (일명 게시물 목록)은 이미입니다 (최소한 (a) 쿼리는 단일 토큰으로 만 구성되며 (b) 반전 된 목록은 압축되지 않은 상태로 저장됩니다.

그러나 일반적으로 (특별히 준비된 경우가 아니면) 접미어 트리에는 일치 목록이 포함되어 있지 않습니다. 따라서 일치하는 동안 트리를 통해 경로를 식별하고 내부 노드에서 끝납니다. 거기에서 그 내부 노드의 하위 트리에있는 모든 경로를 따라 가면 일치의 실제 위치 (일치 당 하나의 리프 노드)를 나타내는 리프 노드를 식별하고 반환하는 결과 목록에 일치 위치를 삽입해야합니다 사용자. 이 마지막 단계는 O (k) 시간이 걸리는 것입니다.

발견 한 내부 노드의 하위 트리에있는 모든 경로를 따라하면 총 복잡도가 O (n + k)보다 훨씬 높은 상당한 시간이 걸릴 수 있습니다. 이는 내부 노드에서 해당 하위 트리의 리프 노드까지 직접 포인터가 있는지 여부에 따라 다릅니다.