암묵적 데이터 구조

Implicit data structure

컴퓨터 과학에서 암묵적인 데이터 구조 또는 공간 효율적인 데이터 구조는 주요 데이터 또는 필수 데이터 외에 매우 적은 정보를 저장하는 데이터 구조입니다. 즉, 낮은 오버헤드를 필요로 하는 데이터 구조입니다.요소들의 위치가 요소들 사이에 의미와 관계를 가지고 있기 때문에 그것들은 "암묵적"이라고 불립니다; 이것은 요소들 사이에 명시적인 관계를 주는 포인터의 사용과 대조됩니다."낮은 오버헤드"의 정의는 다양하지만 일반적으로 일정한 오버헤드를 의미합니다.큰 O 표기로 O(1) 오버헤드를 의미합니다.덜 제한적인 정의는 간결한 데이터 구조이므로 더 큰 오버헤드가 가능합니다.

정의.

암묵적인 데이터 구조는 일정한 O(1) 공간 오버헤드를 갖는 구조입니다(정보 이론상의 하한 이상).

역사적으로, Munro & Suwanda(1980)는 암묵적인 데이터 구조(및 그 하나에 작용하는 알고리즘)를 "구조 정보가 포인터에 명시적이기보다는 데이터가 저장되는 방식에 암묵적인 것"으로 정의했다.정의는 다소 모호하며, 가장 엄밀하게는 단일 어레이로 정의되며, 크기만 유지되거나([1]단일 오버헤드 수), 또는 일정한 오버헤드를 갖는 데이터 구조([2]O(1))로 정의됩니다.후자의 정의는 오늘날 더욱 표준적이며, 일정하지 않지만 작은 o(n) 오버헤드를 가진 데이터 구조의 여전히 느슨한 개념은 Jacobson(1988년)에 의해 정의된 간결한 데이터 구조라고 알려져 있다. Munro & Suwanda([3]1980년)에 의해 반암시적인 것으로 언급되었다.

기본적인 차이는 정적 데이터 구조(읽기 전용)와 동적 데이터 구조(수정 가능) 사이의 차이입니다.정렬된 목록을 배열로 나타내는 것과 같은 단순한 암묵적 데이터 구조는 정적 데이터 구조로서 매우 효율적일 수 있지만, 동적 데이터 구조로서 비효율적일 수 있습니다.이는 정렬된 목록의 경우 수정 작업(예: 삽입)이 비효율적이기 때문입니다.

예

암묵적 데이터 구조의 간단한 예는 배열 데이터 구조입니다.이것은 리스트의 암묵적 데이터 구조이며, 길이의 일정한 오버헤드만을 필요로 합니다.링크 리스트는 각 데이터 요소에 관련된 포인터를 가지며, 한 요소에서 다음 요소로의 관계를 명시적으로 제공합니다.마찬가지로 늘 종단 문자열은 문자열(문자 목록)의 암묵적인 데이터 구조입니다.이들은 정적 데이터 구조(읽기 전용)이기 때문에 매우 단순한 것으로 간주되며, 요소에 대한 반복의 단순 작업만 허용됩니다.

마찬가지로 다차원 배열을 1차원 배열을 치수와 함께 1차원 배열로 표현하는 것도 단순합니다.예를 들어 m × n 배열을 (각 1차원 서브어레이에 대한 포인터의 1차원 배열 대신) m 및 n이라는 숫자와 함께 길이 m·n의 단일 리스트로 나타낸다.요소는 같은 타입일 필요는 없으며 각 필드의 길이가 균일한 한 데이터 테이블(레코드 리스트)을 플랫(1차원) 리스트와 함께 암묵적으로 나타낼 수 있습니다(따라서 각 필드의 크기가 균일한 경우 레코드가 아닌 필드별로 단일 크기를 사용할 수 있습니다).

간단한 예로는 정렬된 배열로 정렬된 목록을 표시하는 것이 있습니다. 이 예에서는 이진 검색을 통해 로그 시간으로 검색할 수 있습니다.로그 시간 검색을 허용하지만 포인터가 필요한 검색 트리, 특히 이진 검색 트리와 대조됩니다.정렬된 배열은 바이너리 검색 트리와 달리 목록 수정이 느리기 때문에 정적 데이터 구조에서만 효율적이며 트리의 공간 오버헤드가 필요하지 않습니다.

암묵적 데이터 구조의 중요한 예는 완전한 이진 트리를 루트, 첫 번째 왼쪽 자식, 첫 번째 오른쪽 자식, 첫 번째 왼쪽 자식 등의 깊이 순으로 리스트로 표현하는 것이다.이러한 트리는 특정 깊이의 조상도에서 두드러지게 발생하며, 암묵적인 표현은 Anentafel(조상표)로 알려져 있다.

이는 완전한 바이너리 트리(마지막 레벨이 불완전할 수 있음)로 일반화할 수 있습니다.이 트리는 priority 큐의 암묵적인 데이터 구조인 바이너리 힙의 가장 잘 알려진 예를 나타냅니다.이는 여러 작업을 수행할 수 있는 효율적인 동적 데이터 구조(데이터를 효율적으로 수정할 수 있음)이기 때문에 이전 예보다 더 정교합니다. 상단뿐만 아니라 삽입 및 팝도 가능합니다.

보다 정교한 암묵적 데이터 구조에는 beap(bi-parental heap)이 있습니다.

역사

가치의 목록이나 표의 사소한 예는 선사시대까지 거슬러 올라가는 반면, 역사적으로 사소하지 않은 암묵적 자료 구조는 적어도 1590년 Michael Eytzinger에 의해 계보에 사용하기 위해 소개된 Anentafel까지 거슬러 올라간다.공식 컴퓨터 과학에서 첫 번째 암묵적 데이터 구조는 일반적으로 컴퓨터 관련 [4][5]주제에 관한 최초의 강의 세트인 무어 학교 강의에서 1946년에 John Mauchly에 의해 소개된 바이너리 검색에 사용되는 정렬된 목록으로 간주됩니다.이 바이너리 힙은 Williams() 오류를 [5]구현하기 위한도움말가 없습니다.암묵적 데이터 구조의 개념은 비프의 [5]도입과 분석의 일환으로 Munro & Suwanda(1980)에서 공식화되었다.

레퍼런스

  1. ^ "따라서 데이터에는 단순한 배열만 필요합니다." 페이지 236; "[ 범위에 있는 포인터와 정수(인덱스)를 공식적으로 구분하지 않습니다.데이터 구조가 암묵적인 경우, 보존할 필요가 있는 정수는 N 자체입니다." , 238
  2. ^ "…항상 다수의 포인터를 유지할 수 있도록 허용하면서도 구조를 암묵적으로 지정하는 것을 선호할 수 있습니다." 페이지 238
  3. ^ "또한 변수라는 점에서 "반암시적"이라고 표현될 수 있는 두 가지 구조를 제안하지만 o(N)는 포인터(인덱스)의 수가 유지된다." 페이지 238
  4. ^ Knuth 1998, § 6.2.1("주문된 표 검색", "이력과 참고 문헌" 하위항. 오류:: 1998
  5. ^ a b c Franceschini, Gianni; Munro, J. Ian (2006). Implicit dictionaries with O(1) modifications per update and fast search. Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms. Miami, FL, United States. pp. 404–413. doi:10.1145/1109557.1109603.

추가 정보

Hervé Brönnimann, J. Ian Munro 및 Greg Frederickson의 출판물을 참조하십시오.