# Character Error Rate (CER) Formula & Theoretical References

เอกสารสรุปสูตรคำนวณ Character Error Rate (CER), อัลกอริทึมเปรียบเทียบตัวอักษร (Alignment Engine) และแหล่งอ้างอิงทางทฤษฎีที่ใช้ในโปรเจกต์ **CER Calculator**

---

## 1. สูตรการคำนวณ CER (Character Error Rate)

$$CER = \left( \frac{S + D + I}{N} \right) \times 100\%$$

หรือแสดงในรูปทศนิยมสัดส่วนข้อผิดพลาด:

$$CER = \frac{S + D + I}{N}$$

### คำอธิบายตัวแปร:
* **$S$ (Substitutions - การแทนที่):** จำนวนตัวอักษรที่ระบบ OCR ทายผิดหรืออ่านสลับเป็นตัวอักษรอื่นเมื่อเทียบกับ Ground Truth
* **$D$ (Deletions - การตกหล่น):** จำนวนตัวอักษรที่มีอยู่ใน Ground Truth แต่ขาดหายไปในผลลัพธ์ OCR
* **$I$ (Insertions - การเพิ่มเกิน):** จำนวนตัวอักษรที่ไม่มีอยู่ใน Ground Truth แต่ปรากฏเกินมาในผลลัพธ์ OCR
* **$N$ (Total Reference Characters - จำนวนตัวอักษรทั้งหมด):** จำนวนตัวอักษรทั้งหมดในไฟล์เฉลย (**Ground Truth**)

> **หมายเหตุ:** ค่า %CER อาจสูงกว่า $100\%$ ได้ในกรณีที่ระบบ OCR ทายตัวอักษรเกินมาเป็นจำนวนมาก ($I > N$)

---

## 2. อัลกอริทึมการเปรียบเทียบข้อความ (Alignment Engine)

การคำนวณหาค่า $S, D, I$ ที่ถูกต้องแม่นยำ จำเป็นต้องเปรียบเทียบข้อความแบบตัวต่อตัวอักษร (Sequence Alignment) โดยในโปรเจกต์ใช้เทคนิคดังนี้:

1. **Levenshtein Edit Distance:**
   * คำนวณระยะทางแก้ไขขั้นต่ำ (Minimum Edit Operations) เพื่อแปลงข้อความจาก Ground Truth ให้ตรงกับ OCR
   * การแก้ไขแต่ละประเภท (Substitution, Deletion, Insertion) มีน้ำหนักต้นทุน (Cost) เท่ากับ $1$ และกรณีตัวอักษรตรงกัน (Match) มีต้นทุนเท่ากับ $0$

2. **Hirschberg's Algorithm (Linear-Space Alignment):**
   * สำหรับข้อความขนาดยาว (เช่น เอกสารที่มีหลายหมื่นตัวอักษร) Dynamic Programming (DP) Matrix ขนาด $m \times n$ จะใช้หน่วยความจำมหาศาล ($O(m \times n)$) และอาจทำให้หน้าเว็บเบราว์เซอร์ค้าง
   * โปรเจกต์นี้จึงประยุกต์ใช้ **Hirschberg's Algorithm** ซึ่งเป็นเทคนิคแบบ *Divide-and-Conquer* รวมกับ DP สองแถวถอยหลัง/ก้าวหน้า (Forward-Backward DP)
   * ทำให้ลดความซับซ้อนด้านพื้นที่ (Space Complexity) ลงเหลือเพียง **$O(m + n)$** ในขณะที่ยังคงเวลาประมวลผล **$O(m \times n)$**

---

## 3. การเชื่อมโยงกับซอร์สโค้ดในโปรเจกต์ (`index.html`)

| ส่วนประกอบ | ฟังก์ชัน/บรรทัดในโค้ด | คำอธิบาย |
| :--- | :--- | :--- |
| **Direct DP Base Case** | [`smallAlignOps()`](../index.html#L231) | ใช้คำนวณ DP alignment แบบตารางสำหรับ Sub-problem ขนาดเล็ก |
| **Linear-Space Row** | [`lastRow()`](../index.html#L273) | คำนวณเฉพาะแถวสุดท้ายโดยใช้ Array เพียง 2 แถว ($O(n)$ space) |
| **Hirschberg Recursion** | [`hirschbergAlign()`](../index.html#L302) | แบ่งครึ่งข้อความอย่างสอดคล้องเพื่อหา Optimal Split Point |
| **CER Engine** | [`computeCER()`](../index.html#L334) | สรุปผลนับ $S, D, I, N$ และคำนวณ %CER ตามสูตร |

---

## 4. แหล่งอ้างอิงทางทฤษฎี (Theoretical References)

1. **Character Error Rate (CER) Standard Benchmark**
   * Morris, A. C., Maier, V., & Green, P. (2004). *From WER to CER*. In Proceedings of the INTERSPEECH 2004 - ICSLP.
   * National Institute of Standards and Technology (NIST). *SCLITE (Score Speech Recognition Results)* Documentation.

2. **Levenshtein Distance**
   * Levenshtein, V. I. (1966). *Binary codes capable of correcting deletions, insertions, and reversals*. Soviet Physics Doklady, 10(8), 707–710.

3. **Hirschberg's Linear Space Alignment**
   * Hirschberg, D. S. (1975). *A linear space algorithm for computing maximal common subsequences*. Communications of the ACM, 18(6), 341–343.