파티션 미세화

Partition refinement

알고리즘 설계에서 파티션 미세화는 데이터 구조로 세트의 파티션을 나타내기 위한 기법으로서, 파티션 세트를 더 많은 수의 작은 세트로 분할하여 파티션을 정제할 수 있게 한다.그런 의미에서 그것은 연합 발견 데이터 구조에 이중적이다. 이 구조는 또한 분리 세트로 파티션을 유지하지만 운영이 세트 쌍을 병합하는 형태다.사전 편찬 범위 우선 검색과 같은 일부 파티션 세분화 애플리케이션에서 데이터 구조는 파티션의 집합에 대한 주문도 유지한다.

파티션 정교화는 DFA 최소화, 병렬 스케줄링을 위한 Coffman-Graham 알고리즘, 그래프 사전 범위 우선 검색을 포함한 그래프와 유한 자동화에 관한 몇 가지 효율적인 알고리즘의 핵심 구성요소를 형성한다.[1][2][3]

데이터 구조

파티션 미세화 알고리즘은 분리형 집합 S를i 유지한다.알고리즘을 시작할 때, 이 패밀리는 데이터 구조에 있는 모든 요소의 단일 집합을 포함한다.알고리즘의 각 단계에서 집합 X가 알고리즘에 제시되며, X의 멤버를 포함하는 패밀리의 집합 S는i 교차로 Si ∩ X와 차이 Si \ X의 두 세트로 분할된다.

그러한 알고리즘은 다음 정보를 대표하는 데이터 구조를 유지함으로써 효율적으로 구현될 수 있다.[4][5]

  • 새 세트를 시퀀스 중간에 삽입할 수 있는 이중 연결 목록과 같은 형태로 패밀리에 있는i 세트 S의 순서
  • 각i 세트 S와i 관련되며, S 요소들의 집합으로, 이중으로 연결된 목록이나 집합에서 개별 요소들을 신속하게 삭제할 수 있는 배열 데이터 구조와 같은 형태로, S 요소들의 집합에서 개별 요소들을 신속하게 삭제할 수 있다.또는, 데이터 구조의 이 구성요소는 모든 집합의 모든 요소를 단일 배열로 저장하고, 그들이 속한 집합의 ID에 따라 정렬하며, 이 배열의 시작 위치와 종료 위치에 따라 집합 S의i 요소 컬렉션을 나타냄으로써 나타낼 수 있다.
  • 각 요소와 연관되어 해당 요소가 속한 집합.

정밀 연산을 수행하기 위해 알고리즘은 주어진 집합 X의 요소를 반복한다.이러한 각 요소 x에 대해 x가 포함된 세트 S를i 찾아 S si X에 대한 두 번째 세트가 이미 시작되었는지 여부를 확인한다.그렇지 않으면 두 번째 세트를 생성하고 작업에 의해 분할된 집합의 목록 L에i S를 추가한다.그 다음, 새로운 집합이 형성되었는지 여부에 관계없이 알고리즘은 S에서i x를 제거하여 Si ∩ X에 추가한다. 모든 원소가 하나의 배열로 저장되는 표현에서 x를i S의 최종 요소와 교환한 다음 새로운i 집합의 시작 지수와 S의 끝 지수를 감소시킴으로써 x를 한 세트에서 다른 세트로 이동시킬 수 있다.마지막으로 X의 모든 요소가 이러한 방식으로 처리된 후 알고리즘은 L을 통해 루프되며, 각 전류 세트i S와 분리된 두 번째 세트 S를 분리하고, 이 두 세트 모두 정교화 연산에 의해 새롭게 형성된 것으로 보고한다.

이러한 방식으로 단일 미세화 작업을 수행하는 시간은 O( X )로, 세트 계열의 요소 수와 무관하며 데이터 구조 내 총 세트 수와도 무관하다.따라서 정제 순서의 시간은 각 정제 단계에서 알고리즘에 주어진 세트의 총 크기에 비례한다.

적용들

파티션 미세화의 초기 적용은 DFA 최소화를 위해 Hopcroft(1971)에 의한 알고리즘에 있었다.이 문제에서 하나는 결정론적 유한 자동 입력으로 주어지며, 가능한 한 적은 상태의 동등한 자동화를 찾아야 한다.Hopcroft의 알고리즘은 입력 자동화의 상태를 하위 집합으로 분할하여 유지하며, 서로 다른 하위 집합에 있는 두 상태가 출력 자동화의 다른 상태에 매핑되어야 하는 속성이 있다.초기에는 두 개의 하위 집합이 있는데, 하나는 자동화의 모든 허용 상태를 포함하고 다른 하나는 나머지 상태를 포함하고 있다.각 단계에서 서브셋 Si 중 하나와 자동화의 입력 기호 x 중 하나를 선택하고, 상태 하위 세트를 x 레이블로 표시된 전환이 S로i 이어지는 상태와 x 변환이 다른 곳으로 이어지는 상태로 세분화한다.이미 선택한 Si 세트가 미세화에 의해 분할된 경우, 결과 두 세트 중 하나(둘 중 더 작은 것)만 다시 선택하면 된다. 이러한 방식으로 각 상태는 O(s log n) 미세화 단계에 대해 X 세트에 참여하고 전체 알고리즘은 O(ns log n)의 시간 O(ns log n)을 필요로 한다. 여기서 n은 초기 상태의 수이고 s는 t의 크기이다.그는 알파벳을 쓴다.[6]

병렬 스케줄링을 위한 Coffman-Graham 알고리즘의 효율적인 구현에 있어서 파티션 미세화가 Sethi(1976)에 의해 적용되었다.Sethi는 그것이 주어진 지시된 Acyclick 그래프의 사전순으로 배열된 위상학적 종류를 선형 시간에 구성하는데 사용될 수 있다는 것을 보여주었다; 이 사전적 위상학적 순서는 Coffman-Graham 알고리즘의 핵심 단계 중 하나이다.이 어플리케이션에서, 분리 집합의 요소들은 입력 그래프의 정점이고, 파티션을 정제하는 데 사용되는 X 세트는 정점의 이웃들의 집합이다.모든 꼭지점의 이웃들의 총 수는 그래프에 있는 가장자리 수일 뿐이기 때문에 알고리즘은 입력 크기인 가장자리 수에서 시간을 선형적으로 사용한다.[7]

파티션 세분화는 또한 사전 편찬 범위 우선 검색, 코드 그래프의 인식에 응용이 있는 그래프 검색 알고리즘과 몇 가지 다른 중요한 등급의 그래프의 주요 단계를 형성한다.다시 말하지만, 분리 집합 원소는 정점이고 집합 X는 이웃들의 집합을 나타내기 때문에 알고리즘에는 선형적인 시간이 걸린다.[8][9]

참고 항목

참조

  1. ^ Paige, Robert; Tarjan, Robert E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062, MR 0917035.
  2. ^ Habib, Michel; Paul, Christophe; Viennot, Laurent (1999), "Partition refinement techniques: an interesting algorithmic tool kit", International Journal of Foundations of Computer Science, 10 (2): 147–170, doi:10.1142/S0129054199000125, MR 1759929.
  3. ^ 하비브, 미셸, 폴, 크리스토프;Viennot, 로랑(1998년),"파티션 개선하는 것엔 종합서:문자열, 그래프, 부울 매트릭스와 automata을 위한 유용한 루틴", 모르반, 미셸에;Meinel, 크리스토프;Krob, 다니엘(eds.), STACS 98:15일 연차 심포지엄 이론적 측면 컴퓨터 과학 프랑스 파리 2월 25–27, 1998년, 호'Proceedings에. (PDF), 강의 노트 컴퓨터 과학으로,. 25–38, doi:10.1007/BFb0028546, 아이 에스비엔 978-3-540-64230-5, MR1650757 1373년, Springer-Verlag, pp vol..
  4. ^ Valmari, Antti; Lehtinen, Petri (2008), "Efficient minimization of DFAs with partial transition functions", in Albers, Susanne; Weil, Pascal (eds.), 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Leibniz International Proceedings in Informatics (LIPIcs), vol. 1, Dagstuhl, Germany: Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, pp. 645–656, arXiv:0802.2826, doi:10.4230/LIPIcs.STACS.2008.1328, ISBN 978-3-939897-06-4, MR 2873773
  5. ^ Knuutila, Timo (2001), "Re-describing an algorithm by Hopcroft", Theoretical Computer Science, 250 (1–2): 333–363, doi:10.1016/S0304-3975(99)00150-4, ISSN 0304-3975
  6. ^ Hopcroft, John (1971), "An n log n algorithm for minimizing states in a finite automaton", Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York: Academic Press, pp. 189–196, MR 0403320.
  7. ^ Sethi, Ravi (1976), "Scheduling graphs on two processors", SIAM Journal on Computing, 5 (1): 73–82, doi:10.1137/0205005, MR 0398156.
  8. ^ Rose, D. J.; Tarjan, R. E.; Lueker, G. S. (1976), "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing, 5 (2): 266–283, doi:10.1137/0205021.
  9. ^ Corneil, 데릭 G.(2004년),"Lexicographic 넓이 우선 탐색 – 조사", Hromkovič, Juraj에, 나 글 씨, 만프레트;Westfechtel, 베른하르트(eds.), Graph-Theoretic 콘텐츠 컴퓨터 과학으로:30일 국제 워크숍 WG 2004년, 배드 Honnef, 독일, 6월장 21-23절, 2004년, 수정된 논문, 강의 노트 컴퓨터 과학으로, Springer-Verlag,를 대신하여 서명함. 1–1 3353 vol..9일 doi:10.1007/978-3-540-30559-0_1.