압축 패턴 매칭

Compressed pattern matching

컴퓨터 과학에서 압축 패턴 매칭(약칭 CPM)은 압축이 거의 또는 전혀 없는 압축 데이터에서 패턴을 검색하는 과정이다.압축된 문자열에서 검색하는 것이 압축되지 않은 문자열을 검색하는 것보다 빠르고 더 적은 공간이 필요하다.

압축 일치 문제

압축 파일이 가변 폭 인코딩을 사용하는 경우 문제가 발생할 수 있다. 예를 들어, "100"을 a의 코드 워드로 하고 "110100"을 b의 코드 워드로 한다.텍스트에서 a의 발생을 찾고 있는 경우, 그 결과 b의 암호문 내에 있는 발생도 얻을 수 있다. 우리는 이 이벤트를 false match라고 부른다.그래서 검출된 발생이 암호문 경계와 효과적으로 일치하는지 검증해야 한다.그러나 우리는 항상 전체 텍스트를 디코딩한 다음 고전적인 문자열 매칭 알고리즘을 적용할 수 있지만, 이것은 일반적으로 더 많은 시간과 공간을 필요로 하며, 예를 들어 압축 파일이 온라인에서 호스팅되는 경우 가능하지 않은 경우가 많다.압축 패턴 매칭 알고리즘에 의해 반환된 일치를 검증하는 이 문제를 전체 텍스트를 해독할 수 없는 것과 함께 참 또는 거짓 일치를 검증하는 문제를 압축 매칭 문제라고 한다.[1]

전략들

코드 워드의 경계를 찾고 텍스트의 완전한 압축을 피하기 위한 많은 전략이 존재한다. 예를 들면 다음과 같다.

  • 이진 검색을 적용할 수 있는 각 코드 워드의 첫 번째 비트 색인 목록
  • 차등 코딩이 있는 각 코드 워드의 첫 번째 비트 색인 목록. 따라서 파일 내에서 공간을 줄일 수 있다.
  • 비트 마스크(비트 1이 각 코드 워드의 시작 비트를 표시하는 경우)
  • 부분 및 목표 감압에 대한 블록 분할.

문자열과 패턴 길이 증가에 따라 로그적으로 성장하는 실행 시간을 제공하는 알고리즘이 도입됐다.[2]

참조

  1. ^ Joel Grus (2019). Data Science from Scratch. First Principles with Python. ISBN 9781491901427.
  2. ^ Artur Jeż (2013-06-25). "Faster fully compressed pattern matching by recompression". arxiv.org. arXiv:1111.3244.

외부 링크