ทำความเข้าใจการเรียงลำดับหน้า PDF: บทสรุปเกี่ยวกับ Page Tree

เอกสาร PDF ไม่ได้จัดเก็บหน้าต่างๆ ไว้ในรายการแบบแบนราบ (flat list) ไม่มีอาร์เรย์ใดที่ดัชนีศูนย์เก็บหน้าแรก และดัชนีสิบเก็บหน้าที่สิบเอ็ด แต่รูปแบบไฟล์จะจัดการหน้าต่างๆ ให้อยู่ในโครงสร้างที่เรียกว่า Page Tree (ISO 32000-1 §7.7.3) แทน สำหรับนักพัฒนาซอฟต์แวร์ที่ต้องการดึงหน้าโดยใช้หมายเลขตรรกะ (logical number) สิ่งนี้หมายความว่าทุกๆ การค้นหาจำเป็นต้องมีการเยี่ยมชมโหนด (traversal) และหากทำผิดวิธีก็จะเปลี่ยนงานส่งออก (export) ง่ายๆ ให้กลายเป็นกับดักประสิทธิภาพแบบ \(O(N^2)\)

บทความนี้จะครอบคลุมถึงวิธีที่ tree จัดการเรียงหน้าต่างๆ, สาเหตุที่การค้นหาดัชนีตามลำดับไม่สามารถปรับขนาดเพื่อรองรับจำนวนที่เพิ่มขึ้นได้ดีนัก, และรูปแบบการเยี่ยมชมโหนดมาตรฐานเพื่อคลี่โครงสร้างให้แบนราบอย่างมีประสิทธิภาพ

โครงสร้างของ Page Tree

โครงสร้าง tree เริ่มต้นที่โหนดราก (root node) ซึ่งระบุตำแหน่งผ่านทาง /Pages ในแคตตาล็อกเอกสาร โหนดใน tree จะมีสองประเภท ได้แก่: Page Tree Nodes (โหนดตัวกลาง, ประเภท /Pages) และ Page Objects (โหนดใบ, ประเภท /Page)

โหนดตัวกลางจะไม่มีเนื้อหาของหน้าอยู่ภายใน แต่มันจะมีอาร์เรย์ /Kids ที่เก็บการอ้างอิงไปยังโหนดลูกๆ ของมัน และจำนวนเต็ม /Count ซึ่งจะรายงานจำนวนรวมของโหนดใบ (หน้าเอกสาร) ที่อยู่ภายในทรีย่อย (subtree) ทั้งหมดที่อยู่ภายใต้มัน โหนดใบจะมีพจนานุกรมหน้า (page dictionary) ของจริงบรรจุอยู่ (เนื้อหา, ทรัพยากร, media box) และจะไม่มีโหนดลูก

ลำดับทางตรรกะของเอกสารคือการเยี่ยมชมแบบ depth-first traversal ของ tree จากซ้ายไปขวา ในการหา "หน้า 1" คุณจะต้องเริ่มจากราก (root) เดินลงไปยังลูกตัวแรกของอาร์เรย์ /Kids ทุกอัน และโหนดใบแรกที่คุณชนก็คือหน้าแรกของเอกสาร

ทำไมการค้นหาดัชนีจึงขยายขนาดได้ไม่ดี

ไลบรารี PDF หลายแห่งมีเมธอดแบบ GetPage(Index) ไว้ให้ใช้งาน เมื่อผู้ใช้ต้องการแยกหน้าทั้งหมด โค้ดที่เข้าใจง่ายจะมีหน้าตาประมาณนี้:

// The naive extraction loop
for (int i = 0; i < document.PageCount(); i++) {
    PdfDictionary* page = document.GetPage(i);
    ExportPage(page);
}

หากไลบรารีทำการ implement ตัว GetPage(i) ด้วยการเดินตามสายของ tree จากรากใหม่ทุกครั้ง ลูปนี้จะกลายเป็น \(O(N \log N)\) สำหรับ tree ที่สมดุล (balanced tree) และจะเป็น \(O(N^2)\) สำหรับ tree ที่ไม่สมดุลอย่างมาก ในเอกสารที่มีความยาว 10,000 หน้า ตัว parser อาจต้องเข้าเยี่ยมชมโหนดตัวกลางนับล้านครั้งเพียงเพื่อวนซ้ำหน้าเอกสารเพียงรอบเดียว

ค่า /Count ช่วยให้ฟังก์ชัน GetPage(i) ที่ฉลาดสามารถข้ามบางกิ่งก้าน (branches) ไปได้ หากลูกตัวแรกมีค่า /Count เท่ากับ 50 และคุณกำลังค้นหาหน้าที่ 75 ตัว parser สามารถนำ 50 ไปลบออกจากดัชนีเป้าหมายแล้วย้ายไปยังลูกตัวที่สอง เพื่อค้นหาหน้าที่ 25 ภายในกิ่งนั้น ซึ่งวิธีนี้ช่วยหลีกเลี่ยงการเจาะลึกลงไปในกิ่งแรกได้อย่างสมบูรณ์ อย่างไรก็ตาม แม้ว่าจะมีการข้ามกิ่งก้านแล้วก็ตาม แต่การเรียกใช้ GetPage(i) ซ้ำๆ ในลูป จะทำให้ระบบทิ้งบริบทของการค้นหาครั้งก่อนหน้าไป ทำให้ต้องเริ่มไต่ระดับลงมาจากรากใหม่อีกครั้ง

การทำให้ Tree แบนราบ: รูปแบบการเยี่ยมชมโหนด

ในการวนซ้ำหน้าทั้งหมดอย่างมีประสิทธิภาพ parser ควรทำให้ tree แบนราบ (flatten) ภายในขั้นตอนเดียว การใช้ depth-first search (DFS) จะเข้าเยี่ยมชมทุกโหนดเพียงครั้งเดียว ซึ่งใช้เวลา \(O(N)\) ในการรวบรวมโหนดใบทั้งหมดตามลำดับการอ่านทางตรรกะ เนื่องจากกราฟ PDF สามารถมีวงจรความซ้ำซ้อน (cycles) ได้ (เช่น ไฟล์ที่ผิดรูปแบบซึ่งโหนดระบุชื่อโหนดแม่ของตนให้เป็นโหนดลูก) การเยี่ยมชมที่แข็งแกร่ง (robust traversal) จะต้องมีการติดตามโหนดที่เคยเยี่ยมชมแล้ว หรือจำกัดความลึกเอาไว้

ต่อไปนี้คือรูปแบบมาตรฐานของ C++ ในการแยกอาร์เรย์พจนานุกรมของหน้าที่ถูกเรียงลำดับออกมา:

void FlattenPageTree(PdfDictionary* node, std::vector<PdfDictionary*>& pages, 
                     std::set<PdfDictionary*>& visited, int depth) {
    if (!node || depth > 32) return; // Prevent stack overflow on malformed files
    
    // Cycle detection
    if (visited.find(node) != visited.end()) return;
    visited.insert(node);
    
    PdfName* type = node->GetName("Type");
    if (type && type->Value() == "Page") {
        // Leaf node reached
        pages.push_back(node);
    } 
    else {
        // Intermediate node (Type /Pages)
        PdfArray* kids = node->GetArray("Kids");
        if (kids) {
            for (int i = 0; i < kids->Size(); i++) {
                PdfDictionary* child = kids->GetDictionary(i);
                FlattenPageTree(child, pages, visited, depth + 1);
            }
        }
    }
}

// Usage:
std::vector<PdfDictionary*> orderedPages;
std::set<PdfDictionary*> visitedNodes;
FlattenPageTree(documentRootPagesNode, orderedPages, visitedNodes, 0);

การทำงานเพียงรอบเดียวนี้จะให้รายการ PdfDictionary* pointers แบบแบนราบ เมื่อถูกคลี่ให้แบนราบแล้ว การปฏิบัติการต่างๆ เช่น การแสดงผลทั้งเอกสาร (rendering), การค้นหาข้ามทุกหน้า, หรือการแยกไฟล์ ก็สามารถวนซ้ำ (iterate) อาร์เรย์ได้ที่ความเร็ว \(O(1)\) ต่อหน้า เมื่อต้องสร้างหรือแก้ไข PDF ก็จะใช้วิธีในทางกลับกัน: รายการแบบแบนราบจะถูกจัดการแก้ไข และจะมีการสร้าง tree ใหม่อีกครั้งในระหว่างขั้นตอนการบันทึก โดยจะปรับสมดุลของโหนด (balancing) เพื่อให้ความลึกของกิ่งก้าน (branch depths) นั้นตื้นที่สุด

หมายเหตุ: ไลบรารีการจัดการเอกสารอย่าง PDFlibPas และ PDFium Component ได้ทำการซ่อนความซับซ้อน (abstract) ของโครงสร้างนี้ไว้ โดยการทำการเยี่ยมชมโหนดแบบแบนราบไว้ในเบื้องหลัง เพื่อให้ Document.Pages[Index] สามารถเข้าถึงหน้าที่ถูกแยกวิเคราะห์ไว้แล้วด้วยความเร็วระดับ \(O(1)\)