boo and replace-string "\\ldots" "\\ldots{}"

[vspell.git] / thesis / main.tex

\documentclass[a4paper,oneside,12pt]{book} % -*- coding: vietnamese-utf8 mode: latex -*-
\usepackage[utf8]{vietnam}
\renewcommand{\rmdefault}{utm}
\renewcommand{\sfdefault}{uhv}
\renewcommand{\ttdefault}{ucr}

\usepackage[hmargin={2cm,2.5cm}]{geometry}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage[vietnam]{minitoc}
\usepackage{tabularx}
\usepackage{footnote}
\usepackage{tipa}
\usepackage{subfigure}

\usepackage{theorem}
\theoremstyle{break}
\newtheorem{algo}{Thuật toán}

\setlength{\parskip}{1.6ex plus 0.7ex minus 0.6ex}

\setcounter{minitocdepth}{4}

\newcommand{\note}[1]{\underline{#1}}
\newcommand{\comment}[1]{}

\title{Chương trình bắt lỗi chính tả tiếng Việt}
\author{Nguyễn Thái Ngọc Duy\\0012020}

\begin{document}
\dominitoc
%\doparttoc
\maketitle

\begin{titlepage}
  \begin{center}
    \Large Lời cảm ơn
  \end{center}
Xin chân thành cám ơn TS. Đinh Điền và các thành viên trong nhóm VCL
đã hỗ trợ hoàn thành luận văn này.
\begin{flushright}
  Nguyễn Thái Ngọc Duy
\end{flushright}
\end{titlepage}

\tableofcontents
%\listoffigures
%\listoftables
%\large%

%% \chapter{Giới thiệu}
%% \label{cha:intro}
%% \begin{center}

%% I kept the right ones out

%% And let the wrong ones in

%% Had an angel of mercy

%% To see me through all my sins

%% There were times in my life

%% When I was goin' insane

%% Tryin' to walk through the pain

%% ****

%% And when I lost my grip

%% And I hit the floor

%% Yeah, I thought I could leave

%% But couldn't get out the door

%% I was so sick n' tired

%% Of livin' a lie

%% I was wishing that I would die

%% ****

%% It's amazing

%% With the blink of an eye

%% You finally see the light

%% It's amazing

%% That when the moment arrives

%% You know you'll be alright

%% It's amazing

%% And I'm saying a prayer

%% To the desperate hearts tonight


%% ****


%% That one last shot's a Permanent Vacation

%% And a how high can you fly with broken wings

%% Life's a journey - not a destination

%% And I just can't tell just what tomorrow brings


%% ****


%% You have to learn to crawl

%% Before you learn to walk

%% But I just couldn't listen

%% To all that righteous talk

%% I was out on the street

%% Just tryin' to survive

%% Scratchin' to stay alive


%% ****


%% ``To all of you people out there

%% Wherever you are - remember:

%% The light at the end of the tunnel

%% May be you - goodnight''
%%\end{center}

\chapter{Tổng quan}
\label{cha:overview}
\minitoc


Ngôn ngữ là một phần quan trọng của đời sống, là phương tiện chuyển
tải thông tin trong đời sống. Trong thời đại bùng nổ thông tin hiện
nay thì ngôn ngữ đóng vai trò hết sức quan trọng, đặc biệt là ngôn ngữ
viết. 

% Tại sao lại làm đề tài này? (Đặt vấn đề)
Khi viết, đôi khi ta mắc phải những lỗi sai chính tả. Chữ quốc ngữ
chịu ảnh hưởng mạnh của ngôn ngữ nói. Một số âm tiết lại rất dễ 
lầm lẫn, khó phân biệt rõ ràng. Ngôn ngữ nói ở những vùng khác nhau lại
có những dị biệt riêng. Những dị biệt này rất dễ gây ra
những lỗi chính tả khi viết nếu người viết không hiểu rõ về tiếng
Việt.

Những thao tác chuyển thông tin ở dạng khác thành văn bản cũng có thể
gây ra lỗi chính tả. Ví dụ, nếu nhập liệu không cẩn thận dẫn đến lỗi
sai chính tả. Khi ghi lại lời nói của người khác mà người đó sử dụng
giọng địa phương cũng có thể dẫn đến lỗi chính tả. Quét các văn bản
giấy thành văn bản điện tử, sử dụng chương trình nhận dạng chữ, cũng
có thể dẫn đến lỗi chính tả do chương trình nhận dạng nhầm lẫn~\ldots{}

Văn bản dễ bị sai chính tả do nhiều yếu tố khách quan. Để kiểm lỗi
chính tả những văn bản này đòi hỏi nhiều công sức và thời gian, đặc
biệt khi khối lượng văn bản bùng nổ như hiện nay. Do đó cần có một
công cụ hỗ trợ kiểm lỗi chính tả, giúp nhanh chóng phát hiện lỗi chính
tả và đề nghị cách khắc phục.

Trong thời đại tin học hoá, máy tính được tận dụng để giảm thiểu công
sức của con người, đồng thời tăng tính hiệu quả. Tin học đã được áp
dụng trong nhiều lĩnh vực khác nhau và chứng tỏ tính hiệu quả của
nó. Tuy nhiên, việc ứng dụng tin học nhằm hỗ trợ bắt lỗi
chính tả tiếng Việt chỉ mới được bắt đầu trong thời gian gần
đây. Những ứng dụng bắt lỗi chính tả hiện có vẫn còn khá đơn
giản, chưa đáp ứng được nhu cầu thực tế. Luận văn này đề ra một giải
pháp khác để bắt lỗi chính tả, với hy vọng góp phần nâng cao chất
lượng ứng dụng bắt lỗi chính tả tiếng Việt bằng máy tính.

\section{Nội dung bài toán}

Bài toán có thể được phát biểu như sau:
Cho một văn bản tiếng Việt. Tìm tất cả các từ sai chính tả trong văn bản
và đề nghị cách giải quyết lỗi nếu có.

% Phạm vi bài toán

Do ngôn ngữ là một lĩnh vực quá rộng. Việc bắt lỗi chính tả tiếng Việt
tổng quát là cực kỳ khó khăn. Do vậy đề tài này chỉ giới hạn bắt lỗi
chính tả trong các văn bản hành chính.

Chỉ sử dụng từ điển từ, từ điển tiếng và ngữ liệu thô làm đầu vào.

Khái niệm từ ở đây là ``từ từ điển'' --- tức là các từ đơn, từ ghép,
cụm từ được lưu trong từ điển. 

Lỗi chính tả ở đây bao gồm chủ yếu hai loại lỗi sau:
\begin{itemize}
\item Lỗi nhập liệu sai: lỗi gõ thiếu chữ, gõ dư chữ, gõ nhầm vị trí
  hai chữ liên tiếp nhau, gõ nhầm một chữ bằng một chữ khác, sai sót
  do bộ gõ tiếng Việt~\ldots{}
\item Lỗi phát âm sai: chủ yếu là do đặc điểm phát âm của từng vùng,
  dẫn đến sai chính tả khi viết.
\end{itemize}

Không xử lý lỗi từ vựng, lỗi cú pháp.

Giả định rằng, nếu từ bị sai chính tả, thì chỉ sai bởi một trong những
lý do nêu trên {\em một lần}. Nghĩa là không xét những trường hợp sai
chính tả, vừa gõ nhầm chữ này bằng chữ khác, vừa gõ dư chữ.

Giả định người dùng chỉ sử dụng một trong hai cách gõ tiếng Việt là
VNI hoặc TELEX.

Văn bản tiếng Việt được coi là thuần Việt. Không kiểm tra chính tả đối
với những từ nước ngoài. Những từ nước ngoài và các ký hiệu khác đều
bị coi là sai chính tả. 

\section{Đặc điểm}

Bắt lỗi chính tả, xét từ quan điểm tin học, là một bài toán khó. Khó
bởi vì ngôn ngữ là một phần rất quan trọng của đời sống xã hội, nó bao
hàm rất nhiều khía cạnh của văn hoá, xã hội. Ngôn ngữ dùng để diễn đạt
suy nghĩ, chuyển tải thông tin, nên nó chứa đựng một khối lượng tri
thức đồ sộ. Để xử lý ngôn ngữ tự nhiên một cách đúng đắn đòi hỏi một
trình độ nhất định. Bởi vậy, việc giải quyết bài toán bắt lỗi chính tả
bằng máy tính là hết sức khó khăn.

Bắt lỗi chính tả đôi khi được mở rộng để phát hiện những lỗi khác
trong văn bản như lỗi cú pháp, lỗi từ vựng~\ldots{} Điều này cũng dễ
hiểu vì người sử dụng cần một chương trình giúp họ phát hiện và loại
bỏ tất cả các lỗi trong văn bản, không quan trọng lỗi đó thuộc loại
lỗi nào. Thông thường những lỗi từ vựng thường bị nhầm lẫn với lỗi
chính tả, buộc chương trình bắt lỗi chính tả phải phát hiện cả lỗi từ
vựng. Đây là một vấn đề khó vì để bắt lỗi từ vựng, đôi khi cần phải
hiểu nội dung cả văn bản.

Nếu tìm hiểu sâu hơn về bài toán này, ta lại gặp một khó khăn khác do
bản chất của tiếng Việt. Đối với tiếng Việt, cũng như một số
ngôn ngữ châu Á khác, một từ chính tả có thể không tương ứng với một
``từ'' trên văn bản. Đối với các thứ tiếng châu Âu, ta có thể dễ dàng
nhận ra một từ, do các từ được phân cách bằng khoảng trắng. Điều đó
không đúng với tiếng Việt. Trong tiếng Việt, các tiếng được phân cách
bởi khoảng trắng, không phải các từ. Điều này dẫn đến một bài toán
mới: tách từ trong tiếng Việt. Do tiếng Việt là ngôn ngữ nói sao viết
vậy, nên rất ít khi gặp lỗi sai về tiếng. Đa số các lỗi chính tả là
lỗi sai từ, nên việc xác định đâu là từ cực kỳ quan trọng.

Vấn đề càng trở nên khó khăn hơn khi phải thực hiện cùng lúc hai bài
toán là tách từ tiếng Việt và kiểm tra chính tả. Thật sự là tách từ
tiếng Việt trước, sau đó bắt lỗi chính tả. Tuy nhiên, do khi tách từ
thường ngầm định là dữ liệu đúng chính xác. Nên khi phải tách từ trước
bước kiểm tra chính tả, ngầm định trên không còn đúng. Bài toán tách
từ trở thành một bài toán khác, phức tạp hơn.

Do tài nguyên ngữ liệu tiếng Việt, đặc biệt là ngữ liệu tiếng Việt
trên máy tính vẫn còn hạn chế, đề tài này chỉ sử dụng các cách hình
thành lỗi chính tả, từ điển từ tiếng Việt và ngữ liệu văn bản dạng
thô. Việc không thể áp dụng được những thông tin cấp cao hơn như từ
loại, cú pháp, ngữ nghĩa~\ldots{} sẽ làm hạn chế đáng kể khả năng của
chương trình.

%% Dùng sai từ là lỗi từ vựng

\section{Hướng giải quyết}

% Bối cảnh %%%%Nổ thêm về bối cảnh ở đây. Cố để lấn qua trang kế%%%

Bài toán bắt lỗi chính tả đã được tìm hiểu từ rất lâu. Tuy nhiên đa số
đều tập trung vào các ngôn ngữ phổ dụng ở châu Âu. Trong khi đó các ngôn
ngữ châu Á, đặc biệt là tiếng Việt, có những đặc trưng riêng, đặt ra
nhiều thách thức mới. Bài toán bắt lỗi chính tả trên các ngôn ngữ châu
Á như tiếng Trung Quốc, tiếng Hàn Quốc, tiếng Nhật, tiếng Thái và tiếng Việt
chỉ bắt đầu được nghiên cứu gần đây.

Đối với các ngôn ngữ châu Âu, cách giải quyết đơn giản là dựa vào từ
điển. Nếu một từ trên văn bản không có trong từ điển nghĩa là từ đó
sai chính tả.

Đối với các ngôn ngữ như tiếng Trung Quốc, tiếng Nhật~\ldots{}, nhiều
giải pháp được đề ra để giải quyết bài toán. Tuy nhiên hầu hết các
giải pháp đều dựa trên ý tưởng áp dụng tập nhầm lẫn để phát sinh các
từ gần đúng, sau đó sử dụng mô hình ngôn ngữ để định lượng, xác định
xem từ nào là đúng nhất.


Đề tài này áp dụng cách giải quyết truyền thống, so sánh từ dựa trên
từ điển. Nếu từ không có trong từ điển nghĩa là sai chính tả, từ đó
đưa ra những gợi ý thích hợp.

Bài toán đặt ra một bái toán con khác là tách từ tiếng Việt trong điều
kiện văn bản bị sai chính tả. Cách giải quyết bài toán này là phát sinh
mọi cách tách từ có thể, sử dụng tập nhầm lẫn, và sau đó áp dụng mô hình
ngôn ngữ để tìm ra cách tách từ đúng nhất. Tập nhầm lẫn được phát sinh
dựa vào nguồn gốc gây lỗi. Các lỗi về phát âm sẽ dựa trên các thói
quen phát âm của từng vùng để tạo tập nhầm lẫn. Các lỗi về nhập liệu
sẽ dựa trên các nghiên cứu về lỗi nhập liệu để đưa ra tập nhầm lẫn
tương ứng.


\section{Bố cục luận văn}

Luận văn được chia thành các chương sau:
\begin{itemize}
\item Chương 1 giới thiệu chung về luận văn, các vấn đề cần giải
  quyết, đặc điểm, phạm vi của bài toán và hướng giải quyết.
\item Chương 2 trình bày cơ sở lý thuyết ngôn ngữ học.
\item Chương 3 trình bày cơ sở lý thuyết toán học/tin học. Các mô hình
  được áp dụng để giải quyết bài toán.
\item Chương 4 trình bày mô hình đề nghị cho bắt lỗi chính tả tiếng Việt.
\item Chương 5 trình bày các chi tiết khi cài đặt chương trình.
\item Chương 6 tóm tắt luận văn, các kết quả đạt được, tìm hiểu các
  đặc điểm của mô hình   cũng như chương trình cài đặt, các hạn chế và
  các hướng giải quyết   trong tương lai.
\item Phần phụ lục trình bày XXX.
\end{itemize}

\chapter{Cơ sở lý thuyết ngôn ngữ}
\label{cha:vietnamese}
\minitoc


\section{Âm tiết}

Ngôn ngữ là một hệ thống tín hiệu. Khi nói, vỏ vật chất của tín hiệu
là âm thanh, khi viết nó được thể hiện bằng chữ. Không phải chữ viết
lúc nào cũng phản ánh chính xác các âm tố tương ứng. Vì vậy, các âm tố
được biểu diễn bằng những ký hiệu đặc biệt, gọi là phiên âm. Các ký
hiệu phiên âm thường đặt giữa \textipa{/\quad/} hoặc
\textipa{[\quad]}.

Âm thanh trong tự nhiên được tạo thành nhờ sự rung động của một vật
thể đàn hồi. Âm thanh của tiếng nói được hình thành nhờ ``bộ máy phát
âm'' của con người --- bao gồm môi, răng, lưỡi, khoang miệng, khoang
mũi, yết hầu, thanh hầu, phổi~\ldots{}. Ngoài ra, tai người chỉ có thể
tiếp nhận một khoảng âm thanh nhất định. Những chấn động không nghe
được gọi là siêu âm và âm ngoại.

Âm học phân biệt các âm thanh theo những đặc trưng khác nhau, bao gồm:
độ cao, độ mạnh, độ dài. Độ cao phụ thuộc vào tần số dao động. Tần số
dao động càng lớn thì âm thanh càng cao. Tai người có khả năng nhận
biết độ cao trong khoảng từ 16 đến 20.000 $H_z$. Độ mạnh (cường độ)
phụ thuộc vào biên độ dao động. Biên độ càng lớn, âm thanh càng
to. Cường độ âm thanh trong ngôn ngữ đảm bảo sự xác minh trong giao tế
và là cơ sở để tạo thành các kiểu trọng âm khác nhau. Độ dài (trường
độ) là khoảng thời gian kéo dài của âm thanh. Ngôn ngữ chỉ quan trọng
thời gian tương đối của âm thanh. Ví dụ, các nguyên âm có trọng âm
thường dài hơn nguyên âm không có trọng âm.


\subsection{Nguyên âm và phụ âm}

Các âm tố có thể chia thành nguyên âm và phụ âm, dựa vào các đặc điểm
âm học, cấu âm và vai trò trong cấu tạo âm tiết.

Nguyên âm có đặc điểm cấu tạo:
\begin{itemize}
\item Luồng hơi ra tự do, không bị cản trở, không có vị trí cấu âm.
\item Bộ máy phát âm căng thẳng toàn bộ.
\item Luồng hơi ra yếu.
\end{itemize}

Phụ âm có đặc điểm cấu tạo hoàn toàn trái ngược với nguyên âm:
\begin{itemize}
\item Luồng hơi bị cản trở do sự xuất hiện chướng ngại trên lối ra của
  luồng không khí, chướng ngại thường xuất hiện ở các khoang trên
  thanh hầu do các khí quan tiếp xúc nhau hay nhích gần nhau mà thành,
  điểm có chướng ngại được gọi là vị trí cấu âm của phụ âm.
\item Bộ máy phát âm không căng thẳng toàn bộ mà sự căng thẳng cơ thịt
  tập trung ở vị trí cấu âm.
\item Luồng hơi ra mạnh.
\end{itemize}

Nguyên âm và phụ âm có chức năng khác nhau trong cấu tạo âm tiết. Các
nguyên âm thường làm hạt nhân hay đỉnh của âm tiết, còn phụ âm thường
là yếu tố đi kèm, không tạo thành âm tiết (trừ các âm phụ vang).

Những âm tố có đặc tính giống nguyên âm nhưng thường chỉ đi kèm, bản
thân không tạo thành âm tiết được gọi là {\em bán nguyên âm}. Ví dụ,
các âm tố viết là u, i trong các âm ``sau'', ``mai'' trong tiếng Việt.


\subsection{Âm vị}

Âm vị là đơn vị nhỏ nhất của cơ cấu âm thanh ngôn ngữ, dùng để cấu tạo
và phân biệt hình thức ngữ âm của những đơn vị có nghĩa của ngôn ngữ
--- từ và hình vị. Ví dụ, các từ ``tôi'' và ``đôi'', ``ta'' và ``đa''
được phân biệt bởi các âm vị \textipa{/t/} và \textipa{/d/}.

Âm vị là đơn vị nhỏ nhất, vì về mặt tuyến tính nó không thể phân chia
nhỏ hơn nữa. Nếu thay âm vị này bằng âm vị khác trong cùng một bối
cảnh ngữ âm sẽ làm cho từ thay đổi nghĩa hoặc mất nghĩa. Ví dụ, thay
âm \textipa{/t/} trong từ ``toàn'' bằng âm \textipa{/h/} sẽ được
``hoàn'' có nghĩa khác, hoặc nếu thay bằng âm \textipa{/n/} sẽ được
``noàn'' hoàn toàn vô nghĩa.

Âm vị có thể được so sánh như những viên gạch trong việc xây dựng mỗi
ngôn ngữ. Các viên gạch thường giống nhau, nhưng các âm vị về nguyên
tắc phải khác nhau, ít nhất ở một đặc trưng nào đó. Sự khác biệt này
tạo ra khác biệt về hình thức âm thanh của hình vị và từ, tạo ra tín
hiệu khác biệt đối với sự thụ cảm của con người. Vậy âm vị có hai chức
năng cơ bản là {\em chức năng khu biệt} (vỏ âm thanh của hình vị và
từ) và {\em chức năng cấu tạo} (chất liệu để cấu tạo nên
những thành tố của những đơn vị có nghĩa).


\subsection{Âm tiết}

Chuỗi lời nói của con người được chia ra làm những khúc đoạn khác
nhau, từ lớn đến nhỏ. Âm tiết là đơn vị phát âm nhỏ nhất, được phân
định tự nhiên trong lời nói con người.

Về phương diện phát âm, dù lời nói chậm đến đâu cũng chỉ phân chia đến
giới hạn của âm tiết mà thôi. Nhưng về phương diện thính giác thì âm
tiết là một tổ hợp âm thanh, có thể gồm nhiều âm tố hoặc đôi khi chỉ
có một âm tố. Mỗi âm tiết chỉ có một âm tố âm tiết tính (có khả năng
tạo thành âm tiết), còn lại là những yếu tố đi kèm, không tự mình tạo
thành âm tiết. Âm tố âm tiết tính thường được phân bố ở đỉnh hay ở
trung tâm, làm hạt nhân âm tiết, thường là các nguyên âm. Các phụ âm
thường là các yếu tố đi kèm, đứng ngoài biên, hay ở ranh giới của âm
tiết. Đôi khi âm tiết chỉ gồm một nguyên âm.

Trong một số trường hợp, âm tiết có thể có hai hoặc ba nguyên âm. Tuy
nhiên trong số đó chỉ có một nguyên âm tạo đỉnh, các âm tố khác không
tạo thành âm tiết, gọi là bán nguyên âm.

Âm tiết có một số chức năng sau:
\begin{itemize}
\item Âm tiết có chức năng tổ chức chất liệu âm thanh của ngôn ngữ
  bằng cách hợp nhất các âm tố trong một đơn vị phát âm nhỏ nhất.
\item Âm tiết là môi trường để hiện thực hoá các hiện tượng ngôn điệu
  như trọng âm, âm điệu.
\item Âm tiết có chức năng cấu thành tiết điệu của lời nói~\ldots{} Chức
  năng này thể hiện rõ trong ngôn ngữ thơ.
\end{itemize}

Trong các ngôn ngữ âm tiết tính như tiếng Trung Quốc, tiếng Miến Điện,
tiếng Việt~\ldots{} nói chung âm tiết trùng với hình vị --- đơn vị cơ
bản của ngữ pháp. Âm tiết có chức năng là vỏ ngữ âm của hình vị, tạo
nên một đơn vị đặc biệt, gọi là {\em hình tiết}.

Tính chất âm tiết của tiếng Việt đưa đến nhiều hệ quả quan trọng về
ngữ âm cũng như về ngữ pháp. Về mặt ngữ âm, do mỗi âm tiết là vỏ ngữ
âm của một hình vị, và cũng thường là vỏ ngữ âm của từ đơn, nên số
lượng các âm tiết là hữu hạn\footnote{Theo Nguyễn Phan Cảnh ``tiếng
  Việt đưa ra hơn 17.000 âm tiết --- tín hiệu với tự cách là vỏ ngữ âm
khả năng, và chỉ sử dụng hơn 6.900 với tư cách là các âm tiết tồn tại
thực'' (Nguyễn Phan Cảnh, ``Bản chất cấu trúc âm tiết tính của ngôn
ngữ: Dẫn luận vào một miêu tả không phân lập đối với âm vị học Việt
Nam, tạp chí ngôn ngữ, H. 1978, số 2)}.

Là vỏ ngữ âm của một hình vị hay một từ đơn, mỗi âm tiết Tiếng Việt
bao giờ cũng tương ứng với một ý nghĩa nhất định, nên việc phá vỡ cấu
trúc âm tiết trong ngữ lưu, tức xê dịch vị trí các âm tố (âm vị) của
cùng một hình vị từ âm tiết này sang âm tiết khác, là điều ít xảy
ra. Kết quả là trong tiếng Việt, âm tiết có một cấu trúc chặt chẽ, mỗi
âm tố (âm vị) có một vị trí nhất định trong âm tiết. Đứng đầu âm tiết
bao giờ cũng là một phụ âm, cuối âm tiết là một phụ âm hoặc một bán
nguyên âm. Phụ âm cuối luôn luôn ở cuối âm tiết, không thể trở thành
âm đầu được. Do đó, phụ âm cuối và âm đầu làm thành hai đối hệ khác
nhau, có vị trí và chức năng khác nhau trong cấu trúc âm tiết.

Một đặc điểm khác của âm tiết tiếng Việt là mỗi âm tiết đều mang
một thanh điệu nhất định. Việc thể hiện thanh điệu đòi hỏi âm tiết
phải có một trường độ cố định. Tính chất này làm cho các yếu tố bên
trong âm tiết, trừ phụ âm đầu, không có một trường độ cố định, mà đắp
đổi lẫn nhau, liên quan với nhau rất chặt chẽ.


\subsubsection{Cấu trúc âm tiết tiếng Việt}

Trên bình diện ngữ âm học, các cứ liệu thực nghiệm cho thấy âm tiết
Tiếng Việt được cấu tạo bởi ba thành tố độc lập là thanh điệu, phụ âm
đầu và phần còn lại.

Thanh điệu là yếu tố luôn có mặt trong mọi âm tiết tiếng Việt. Tính
chất độc lập về mặt ngữ âm của thanh điệu thể hiện ở chỗ nó có đường
nét và trường độ tương đối ổn định tùy thuộc vào các loại hình âm
tiết.

Phụ âm đầu là yếu tố mở đầu của âm tiết. Tính chất độc lập của phụ âm
đầu thể hiện ở chỗ nó không tham gia vào việc đắp đổi về trường độ
giữa các yếu tố bên trong âm tiết.

Phần còn lại của âm tiết có từ một đến ba yếu tố, gồm một bán nguyên
âm chiếm vị trí trung gian giữa phụ âm đầu và phần còn lại, một nguyên
âm âm tiết tính và một phụ âm hoặc bán nguyên âm cuối, có vai trò kết
thúc âm tiết. Trừ bán nguyên âm trước nguyên âm tiết tính, các yếu tố
của phần còn lại liên kết với nhau rất chặt chẽ, làm thành một
khối. Để đảm bảo cho tính chất cố định về trường độ của âm tiết, các
yếu tố của phần còn lại có sự đắp đổi nhau về trường độ: nếu nguyên âm
dài thì phụ âm hay bán âm cuối ngắn, ngược lại nếu nguyên âm ngắn thì
âm cuối dài. Các yếu tố của phần còn lại không có một trường độ cố
định, và do đó mức độ độc lập về mặt ngữ âm của chúng thấp hơn so với
phụ âm mở đầu âm tiết. Phần còn lại của âm tiết được gọi là phần vần,
vì đây là bộ phận đoạn tính kết hợp với thanh điệu tạo nên vần thơ.

Tóm lại, các yếu tố của âm tiết tiếng Việt có mức độ độc lập khác
nhau, chia làm hai bậc:

\begin{itemize}
\item Bậc một là những yếu tố độc lập về mặt ngữ âm và có thể được
  tách rời về mặt hình thái học. Đó là thanh điệu, âm đầu và vần.
\item Bậc hai là các yếu tố của phần vần, gồm bán nguyên âm trước
  nguyên âm âm tiết tính (được gọi là âm đệm), nguyên âm âm tiết tính
  (được gọi là âm chính), phụ âm hoặc bán nguyên âm cuối (được gọi là
  âm cuối). Các yếu tố này gắn liền với nhau về mặt ngữ âm do tính
  chất cố định về trường độ của âm tiết và chỉ được tách ra bằng những
  ranh giới thuần túy ngữ âm học.
\end{itemize}

Các thành tố của âm tiết tiếng Việt và quan hệ hai bậc giữa các thành
tố được trình bày trong hình~\ref{fig:cautrucamtiet}.

\begin{figure}[htbp]
  \centering
  \begin{tabular}{|c|c|c|c|}
    \hline
    \multicolumn{4}{|c|}{Thanh điệu}\\\hline
    Âm đầu&\multicolumn{3}{c|}{Vần}\\\cline{2-4}
    &Âm đệm&Âm chính&Âm cuối\\\hline
  \end{tabular}
  \caption{Cấu trúc âm tiết}
  \label{fig:cautrucamtiet}
\end{figure}

%\subsection{Các hiện tượng liên quan đến âm tiết}


%\subsubsection{Nguyên âm đôi}


% Sự biến hoá ngữ âm

Khái niệm âm tiết liên quan mật thiết đến sự biến hoá ngữ âm. Vì các
âm tố lời nói không phát âm đơn lập mà được phát âm trong dòng lời nói
liên tục, cho nên các âm tố có thể ảnh hưởng lẫn nhau, đặc biệt là
những âm tố lân cận được phát âm trong cùng một âm tiết, hoặc ở những
âm tiết đi liền nhau. Một số hiện tượng biến hoá ngữ âm thường gặp
trong tiếng Việt:
\begin{itemize}
\item Sự thích nghi. Xuất hiện giữa phụ âm và nguyên âm đứng cạnh
  nhau. Nếu âm tố sau biến đổi cho giống âm tố đi trước, đó là thích
  nghi xuôi. Nếu âm tố trước biến đổi cho hợp với âm tố sau là thích
  nghi ngược. Trong tiếng Việt, nguyên âm và phụ âm cuối kết hợp với
  nhau rất chặt chẽ, tạo thành vần của âm tiết. Hiện tượng thích nghi
  biểu hiện rõ rệt trong những vần có nguyên âm dòng trước và dòng sau
  tròn môi kết hợp với phụ âm cuối ``ng'' và ``c''.
\item Sự đồng hoá (một yếu tố thay đổi để giống yếu tố kia). Ví dụ,
  ``vỏn vẹn'' và ``vẻn vẹn''.
\item Sự dị hoá (hiện tượng rút gọn cho dễ phát âm). Ví dụ, ``ba mươi
  mốt'' và ``băm mốt''.
\end{itemize}

\subsection{Phụ âm đầu}

Phụ âm đầu luôn gắn liền với vị trí và chức năng mở đầu âm tiết. Đi
sau âm đầu trong âm tiết là bán nguyên âm không thành âm tiết (hay còn
gọi là âm đệm).

Hệ thống phụ âm đầu tiếng Việt với số lưỡng đối lập âm vị học tối đa
được thể hiện trên chữ viết. Riêng những âm tiết như ``ăn'',
``uống''~\ldots{} tuy không ghi phụ âm đầu, nhưng thực tế vẫn tồn tại
phụ âm đầu (âm tắt thanh hầu \textipa{/P/}). Trong từng phương ngữ,
một số đối lập có trên chữ viết có thể bị mất đi hoặc bị thay thế. Ví
dụ, trong tiếng Hà Nội không còn đối lập các phụ âm đầu giữa
ch--tr,x--s và gi,d với r. Trong tiếng miền Nam, \textipa{/v/} và
\textipa{/z/} được thay bằng \textipa{/j/}.

Hiện nay, hệ thống phụ âm đầu được sử dụng thực tế trong nhà trường và
trên các văn bản, chung cho các phương ngữ, là hệ thống phụ âm đầu
hình thành trên cơ sở phát âm Hà Nội với sự phân biệt các phụ âm
ch--tr, x--s, g,gi--r gồm 22 phụ âm sau: \textipa{/b, m, f, v, t,
  t\super{h}, d, n, s, z, l, \:t, \:s, \:z, c, \textltailn, k, N, x,
  G, P, h/}\footnote{Phụ âm \textipa{/p/} gặp trong từ vay mượn hoặc
  phiên âm tiếng nước ngoài, không được đưa vào hệ thống này}

Hệ thống phụ âm đầu của tiếng địa phương miền Bắc, mà cở sở là phát âm
Hà Nội có 19 phụ âm (kể cả âm tắc thanh hầu \textipa{/P/}). Trong phát
âm Hà Nội không có loạt phụ âm uốn lưỡi \textipa{/\:t, \:s, \:z/}. Các
phụ âm này đều được chuyển thành các âm đầu lưỡi hoặc mặt lưỡi tương
ứng \textipa{/c, s, z/}. Ví dụ,
\begin{itemize}
\item ``cha'' và ``tra'' đều phát âm thành ``cha'' \textipa{/ca/}
\item ``sa'' và ``xa'' đều phát âm thành ``xa'' \textipa{/sa/}
\item ``da'', ``gia'' và ``ra'' đều được phát âm thành ``da'' \textipa{/da/}
\end{itemize}

Trong các thổ ngữ vùng Bắc Trung Bộ (Nghệ Tĩnh --- Bình Trị Thiên) còn
giữ loạt các phụ âm cong lưỡi \textipa{/\:t, \:s, \:z/}. Ở một số nơi
thuộc Nghệ Tĩnh, phụ âm ``ph'' được phát âm như âm mặt lưỡi sau bật
hơi \textipa{/k\super{h}/}. Vì vậy hệ thống phụ âm đầu những nơi này
có thêm dãy âm bật hơi \textipa{/p\super{j}, \:t\super{h},
  k\super{h}/}. Trong khi đó các thổ ngữ miền Bắc và miền Nam chỉ còn
lại một âm bật hơi \textipa{/t\super{h}/} mà thôi. Vùng Bình Trị Thiên
không có phụ âm ``nh''. Phụ âm này thường được phát âm thành
\textipa{/j/}. Ví dụ, ``nhà'' được phát âm thành ``dà''. Nếu coi hệ
thống phụ âm đầu vùng Vinh là đại diện cho phương ngự Bắc Trung Bộ thì
hệ thống này có 22 phụ âm đầu.

Hệ thống phụ âm đầu miền Nam (từ đèo Hải Vân trở vào) không có các phụ
âm xát hữu thanh \textipa{/v, z/}. Tương ứng với \textipa{/v, z/}
trong phát âm Hà Nội, phát âm miền Nam có phụ âm mặt lưỡi giữa
\textipa{/j/}. Đôi khi âm \textipa{/v/} được phát âm thành âm môi-môi,
xát, vang ngạc hoá \textipa{/Bj/}. Hiện nay các âm cong lưỡi đang
trong quá trình biến đổi trong tiếng miền Nam. Phụ âm \textipa{/\:s/}
là phụ âm ít bền vững nhất thường được phát âm thành
\textipa{/s/}. Các phụ âm cong lưỡi khác như \textipa{/\:t/} và
\textipa{/\:z/} vẫn còn giữ lại, phân biệt với \textipa{/c/} và
\textipa{/j/} nhưng không đều đặn ở các thổ ngữ. Trong phát âm miền
Nam có phụ âm đầu \textipa{/w/}\footnote{Giá trị âm vị học của
  \textipa{/w/} là vấn đề còn đang bàn cãi} xát, môi-môi, tương ứng
với các phụ âm tắc, lưỡi sau và thanh hầu tiếng Bắc khi kết hợp với âm
đệm \textipa{/-u-/}. Ví dụ, ``qua'' \textipa{/wa/}, ``ngoại''
\textipa{/wai/}, hoa \textipa{/wa/}. Nếu lấy hệ thống phụ âm đầu của
tiếng thành phố Hồ Chí Minh làm cơ sở cho phương ngữ miền Nam thì hệ
thống này có 21 phụ âm đầu.


\subsubsection{Quan hệ phân bố giữa phụ âm đầu và âm đệm}

Âm đệm là thành tố đi sau phụ âm đầu trong âm tiết. Trong tiếng Việt
chỉ có một âm đệm là \textipa{/-u-/}, thể hiện trên chữ viết bằng hai
chữ ``u'' và ``o''. Ví dụ, ``hoa'', ``quế''. Trong phát âm, âm đệm chỉ
được thể hiện ở tiếng địa phương miền Bắc và Bắc Trung Bộ, còn trong
tiếng địa phương miền Nam thường không có âm đệm \textipa{/-u-/}.

Trong phát âm Hà Nội, hầu hết loạt phụ âm lưỡi và thanh hầu có thể
phân bố trước âm đệm. Ví dụ, ``toa'', ``đoán'', ``nhoà''~\ldots{} Riêng
loạt âm môi \textipa{/b, m, v, f/} không phân bố trước âm đệm
\textipa{/-u-/} vì chúng có cấu âm môi giống nhau. Trong tiếng Việt,
hễ những âm có cấu âm giống nhau hay tương tự nhau thì không phân bố
cạnh nhau.

Ngoài các âm môi, một vài phụ âm lưỡi như \textipa{/n, \:z, G/} cũng
rất ít xuất hiện trước âm đệm.

\subsection{Vần}


\subsubsection{Âm đệm}

Trong âm tiết, âm đệm \textipa{/-u-/} đứng sau phụ âm đầu và đứng
trước âm chính. Nó đóng vai trò một âm lướt trong kết cấu âm tiết. Về
mặt cấu âm, âm đệm \textipa{/-u-/} được phát âm giống như nguyên âm
\textipa{[u]} nhưng không làm đỉnh âm tiết. Đó là một bán nguyên âm
môi-ngạc mềm, được phiên âm là \textipa{[-u-]} hay
\textipa{[-w-]}. Động tác cấu âm này diễn ra đồng thời với các giai
đoạn phát âm của phụ âm đầu và phần vần đầu của nguyên âm làm âm
chính. Về mặt âm học, âm đệm \textipa{/-u-/} có tác dụng làm biến đổi
âm sắc của âm tiết, làm trầm hoá âm sắc của âm tiết.

Âm đệm \textipa{/-u-/}, với tính chất là một bán nguyên âm môi-ngạc
mềm, có độ mở rộng hay hẹp tương ứng với độ mở của nguyên âm đi sau
nó. Trước nguyên âm hẹp \textbf{i}, âm đệm \textipa{/-u-/} được thể
hiện bằng một bán âm hẹp tương ứng là \textipa{[u]}, ví dụ
``tuy''. Trước các nguyên âm có độ mở trung bình \textbf{ê, ơ, â}, âm
đệm  \textipa{/-u-/} được thể hiện bằng một bán âm độ mở vừa
\textipa{[o]}, ví dụ ``khuê'', ``huơ'', ``huân''. Trước các nguyên âm
có độ mở rộng \textbf{e, a, ă}, âm đệm  \textipa{/-u-/} được thể hiện
bằng một bán âm có độ mở tương ứng là \textipa{[O]}, ví dụ ``khỏe'',
``khoắn'', ``khoan''.

Âm đệm  \textipa{/-u-/} xuất hiện phần lớn ở các từ gốc Hán như
``thuyền'', ``loan'', ``uyên''. Về mặt phân bố, như đã nói, âm đệm có
thể xuất hiện sau hầu hết các phụ âm đầu, trừ các phụ âm môi
\textipa{/b, m, f, v/}. Sau các phụ âm môi, âm đệm chỉ có mặt trong
một ít từ phiên âm tiếng nước ngoài như ``buýt'', ``phuy'',
``voan''. Ngoài ra, sau các phụ âm \textipa{/n, \:z, G/}, âm đệm
\textipa{/-u-/} cũng chỉ xuất hiện trong một vài từ như ``noãn'',
``roa'', ``goá''.

Âm đệm \textipa{/-u-/} cũng không xuất hiện trước các nguyên âm tròn
môi \textbf{u, uô, ô, o}. Sự phân bố của âm đệm sau phụ âm đầu và
trước các nguyên âm thể hiện một quy luật của ngữ âm tiếng Việt: các
âm có cấu âm giống nhau hoặc gần gũi nhau không được phân bố cạnh
nhau.

Về mặt chữ viết, âm đệm \textipa{/-u-/} được ghi bằng con chữ ``o''
trước ba nguyên âm rộng \textbf{e, a, ă} và được ghi bằng con chữ
``u'' trước các nguyên âm còn lại. Ví dụ, ``thuý'', ``thuê'', ``loe'',
``loa''. Riêng trường hợp sau phụ âm đầu \textipa{/k-/}, âm đệm
\textipa{/-u-/} luôn được ghi bằng con chữ ``u'' dù sau nó là nguyên
âm rộng. Ví dụ: ``quạ'', ``quý'' (trong những trường hợp này âm
\textipa{/k-/} được ghi bằng con chữ ``q'')\footnote{Do đó về mặt chữ
  viết, sau con chữ ``q'', con chữ ``u'' luôn luôn có giá trị là một
  âm đệm. Điều này giúp ta phân biệt ``ua'' là một nguyên âm đôi trong
từ ``của'' với ``ua'' trong tổ hợp âm đệm+nguyên âm trong
``quả''. Riêng trường hợp ``quốc'' thì ``uô'' là nguyên âm đôi nhưng
\textipa{/k-/} vẫn được ghi bằng ``q''. Sự phân biệt về mặt con chữ ở
đây có giá trị phân biệt nghĩa hai từ đồng âm ``cuốc'' và ``quốc'' đều
được phát âm là \textipa{/kuok/}.}.

Âm đệm \textipa{/-u-/}, vốn là yếu tố có mặt trong phương ngữ Bắc và
Bắc Trung Bộ, lại hoàn toàn vắng mặt trong phương ngữ Nam Bộ. Do đó,
cấu trúc âm tiết của phương ngữ Nam Bộ chỉ có ba thành phần đoạn tính:
âm đầu, âm chính, âm cuối.

Sự vắng mặt của âm đệm trong phương ngữ Nam Bộ có thể đưa đến một số
biến đổi ở âm đầu và âm chính. Đáng chú ý là sự biến đổi của các phụ
âm mặt lưỡi sau và thanh hầu, thành các phụ âm môi. Ví dụ, ``hoa''
thành ``wa'', khuya thành ``phia''.

Hiện nay dưới sự ảnh hưởng của ngôn ngữ văn học, đã thấy xuất hiện âm
đệm sau các phụ âm đầu lưỡi, mặt lưỡi giữa và mặt lưỡi sau trong cách
phát âm của tầng lớp trí thức, của giới trẻ, trừ trường hợp hai phụ âm
thanh hầu \textipa{/h-,P-/} và phụ âm mặt lưỡi sau \textipa{/k-/}, vẫn
được phát âm thành \textipa{[w-]} trong các từ ``hoa'', ``oa'',
``qua'' (đều phát âm là \textipa{[wa]}).

\subsubsection{Âm chính}

Âm chính trong âm tiết tiếng Việt có thể là một nguyên âm đơn hoặc một
nguyên âm đôi.


\paragraph{Nguyên âm đơn}

Tiếng Việt có 11 nguyên âm đơn làm âm chính. Căn cứ vào vị trí lưỡi,
hình dáng môi, các nguyên âm đơn được chia ra:
\begin{itemize}
\item Các nguyên âm giòng trước không tròn môi: \textipa{/i, e, E/}.
\item Các nguyên âm giòng sau không tròn môi: \textipa{/W, 7, \v{7},
    a, \v{a}/}.
\item Các nguyên âm giòng sau tròn môi: \textipa{/u, o, O/}.
\end{itemize}

Căn cứ vào độ mở miệng, có thể chia thành:
\begin{itemize}
\item Các nguyên âm có độ mở miệng hẹp: \textipa{/i, W, u/}.
\item Các nguyên âm có độ mở trung bình: \textipa{/e, 7, \v{7}, o/}.
\item Các nguyên âm có độ mở rộng: \textipa{/E, a, \v{a}, O/}.
\end{itemize}

Căn cứ vào âm sắc, có thể chia ra:
\begin{itemize}
\item Các nguyên âm bổng: \textipa{/i, e, E/}.
\item Các nguyên âm trung bình: \textipa{/W, 7, \v{7}, a, \v{a}/}.
\item Các nguyên âm trầm: \textipa{/u, o, O/}.
\end{itemize}

Căn cứ vào trường độ, có thể chia ra:
\begin{itemize}
\item Các nguyên âm dài: \textipa{/i, e, E, W, 7, a, u, o, O/}.
\item Các nguyên âm ngắn: \textipa{/\v{7}, \v{a}/}.
\end{itemize}


\paragraph{Nguyên âm đôi}

Ngoài 11 nguyên âm đơn, còn có 3 nguyên âm đôi âm vị tính là
\textipa{/ie, W7, uo/}.

\subsubsection{Âm cuối}

Âm cuối là yếu tố kết thúc âm tiết. Các âm tiết trong tiếng Việt có
thể kết thúc bằng cách biến đổi âm sắc của âm chính do động tác khép
lại của bộ máy phát âm, làm cho nó bổng hơn hoặc trầm hơn. Âm cuối
trong trường hợp này là hai bán nguyên âm \textipa{/-u/} và
\textipa{/-i/}. Âm tiết tiếng Việt còn có thể kết thúc bằng động tác
khép của bộ máy phát âm với một phụ âm tắc (mũi hoặc miệng).

Hệ thống âm cuối trong tiếng Việt gồm có 2 bán nguyên âm và 6 phụ
âm. Sau phụ âm bao gồm: \textipa{/m, p, n, t, N, k/}.


\subsubsection{Quy luật phân bố của các âm cuối sau âm chính}

Về mặt phân bố, các bán nguyên âm cuối \textipa{/-u/} và
\textipa{/-i/} chỉ xuất hiện sau các nguyên âm không cùng âm sắc với
nó. Bán nguyên âm cuối \textipa{/-i/} chỉ xuất hiện sau các bán nguyên
âm không phải giòng trước. Bán nguyên âm cuối \textipa{/-u/} chỉ xuất
hiện sau các bán nguyên âm không tròn môi. Sự kết hợp giữa nguyên âm
và bán nguyên âm cuối, giống như sự kết hợp giữa âm đệm và nguyên âm
làm âm chính, tuân theo quy luật dị hoá. Theo đó, các âm có cấu âm
giống nhau hoặc gần nhau không bao giờ được phân bố cạnh nhau.

Có thể hình dung khả năng kết hợp giữa nguyên âm làm âm chính với hai
bán nguyên âm cuối \textipa{/-i/} và \textipa{/-u/} như sau:
\begin{itemize}
\item Các nguyên âm có thể đứng trước bán nguyên âm \textipa{/-i/} bao
  gồm các âm biểu hiện bởi các chữ: ư, ươ, ơ, â, a, ă, u, uô, ô, o.
\item Các nguyên âm có thể đứng trước bán nguyên âm \textipa{/-u/} bao
  gồm các âm biểu hiện bởi các chữ: i, iê, ê, e, ư, ươ, ơ, â, a, ă.
\end{itemize}

Các phụ âm cuối khác, nói chung được phân bố đều đặn sau các nguyên
âm, trừ hai âm cuối mũi \textipa{/-m, -p/} không xuất hiện sau
\textipa{/W/}.


\subsubsection{Sự thể hiện của nguyên âm và phụ âm trong các tiếng địa
  phương}

Trong phương ngữ Nam Bộ, các nguyên âm đôi \textipa{/ie, W7, uo/} khi
kết hợp với các âm cuối \textipa{/-i, -u, -m, -p/} được thể hiện thành
các nguyên âm đơn \textipa{/i, W, u/}. Ví dụ, ``chuối'' --- ``chúi'',
``bưởi'' --- ``bửi'', ``tiếp'' --- ``típ''.

Ở một vài địa phương thuộc phương ngữ Trung Bộ, các nguyên âm đôi được
thể hiện bằng các nguyên âm cùng dòng, độ mở rộng. Ví dụ, ``người''
--- ``ngài'', ``ruột'' --- ``rọt'', ``miếng'' --- ``méng''.

Hai phụ âm cuối \textipa{/-n, -t/} được thể hiện thành \textipa{/-N,
  -k/} trong phương ngữ Nam Bộ, khi chúng đi sau các nguyên âm đơn và
đôi, trừ \textipa{/i, e/} là hai nguyên âm giòng trước, độ mở hẹp và
trung bình. Ví dụ, ``đen'' -- ``đeng'', ``đét'' --- ``đéc''.

Sau ba nguyên âm giòng trước \textipa{/i, e, E/}, hai phụ âm
\textipa{/-N, -k/} được thể hiện trong các phương ngữ Nam Bộ thành
\textipa{/-n, -t/}, đồng thời các nguyên âm này có cấu âm lui về phía
sau nhiều hơn so với các nguyên âm trong phương ngữ Bắc Bộ, trở thành
các nguyên âm giòng giữa nghe gần giống như ư, ơ (hoặc â) và ă.

Điểm đáng lưu ý là trong phương ngữ Nam Bộ, sau \textipa{/i, e/} hai
âm cuối \textipa{/-n, -t/} vẫn được phát âm không đổi. Sự khác biệt
trong các vần này giữa phương ngữ Bắc Bộ và Nam Bộ xảy ra ở nguyên âm.

Trong phương ngữ Nam Bộ không có các âm cuối \textipa{/-\textltailn,
  -c/}. Âm cuối này được phát âm thành \textipa{/-n, -t/}.

\subsection{Thanh điệu}

Thanh điệu là đặc trưng ngôn điệu của âm tiết. Người ta gọi thanh điệu
là âm vị siêu đoạn tính. Số lượng thanh điệu trong tiếng Việt khác
nhau giữa các tiếng địa phương. Số lượng nhiều nhất là 6 thanh trong
phát âm Hà Nội, hay trong các tiếng Bắc nói chung, và được phản ánh
trên chữ viết. Đó là các thanh: sắc, huyền, ngã, hỏi, nặng, và thanh
không dấu.

Trong các tiếng địa phương từ Thanh Hoá trở vào Nam thường chỉ có năm
thanh, thanh ngã trùng với thanh hỏi (trong một số vùng Thanh Hoá,
tiếng Bình Trị Thiên, Nam Trung Bộ và Nam Bộ), hoặc thanh ngã trùng
với thanh nặng (trong tiếng vùng Nghệ An, Hà Tĩnh). Ngoài ra trong một
vài thổ ngữ lẻ tẻ ở Nghệ An và Quảng Bình chỉ có 4 thanh điệu.


\subsubsection{Sự phân bố của thanh điệu}

Như đã biết, thanh điệu là đặc tính siêu đoạn của âm tiết. Các đặc
trưng của thanh điệu được thể hiện đồng thời với các thành phần cấu
trúc khác của âm tiết. Vì vậy, trong chừng mực nào đó nó bị chế định
bởi các thành phần này.

Về mặt âm vị học, âm tiết tiếng Việt trước hết được chia thành hai đơn
vị là phụ âm đầu và vần. Phần vần, trong đó có nguyên âm, là phân luôn
luôn mang thanh tính của âm tiết. Các đặc điểm về âm vực và âm điệu
của thanh điệu chỉ được biểu hiện trong phần mang thanh tính mà
thôi. Vì vậy, trong sự đối lập và thống nhất các thanh điệu, phần vần
đóng vai trò quan trọng. Phụ âm đầu hầu như không đóng vai trò gì
trong sự đối lập các thanh. Về mặt ngữ âm, đặc tính của thanh điệu
cũng hầu như không lan truyền lên phụ âm đầu, hoặc có chăng (trong
trường hợp phụ âm đầu hữu thanh) thì trong đoạn đầu của âm tiết, các
đặc trưng khu biệt của thanh điệu cũng chưa thể hiện rõ.

Phần vần có thể bao gồm âm đệm, một âm chính và có thể có bán nguyên
âm hoặc phụ âm cuối. Sự khác nhau của thanh điệu biểu hiện tập trung ở
giữa và cuối vần (tức phần nguyên âm và phụ âm cuối).


Trong các vần không có âm cuối, có âm cuối là bán nguyên âm hoặc phụ
âm vang, các đặc trưng của thanh điệu được thể hiện dễ dàng. 
Với các vần kết thúc bằng các phụ âm cuối vô thanh, khép, các đặc
trưng của thanh được biểu hiện rất hạn chế.
Có thể nói rằng, trong mối quan hệ với các thành phần chiết đoạn của
âm tiết, thanh điệu bị sự chế định rõ ràng nhất của âm cuối. Vì vậy sự
phân bố của thanh điệu trong âm tiết phụ thuộc vào loại hình kết thúc
âm tiết.

Số lượng các thanh điệu xuất hiện trong những âm tiết kết thúc bằng
phụ âm cuối vô thanh rất hạn chế, thường chỉ có thể có thanh sắc hoặc
thanh nặng.

Thanh sắc và thanh nặng trong những âm tiết có âm cuối vô thanh có
những đặc điểm riêng về độ dài và đường nét âm điệu khác với thanh sắc
và thanh nặng trong các âm tiết còn lại. Vì vậy trước đây đã từng có
quan niệm cho rằng các thanh điệu trong các âm tiết có âm cuối vô
thanh là những thanh điệu đặc biệt, tạo thành hệ thống 8 thanh điệu:
tan, tàn, tãn, tản, tán, tạn, tát, tạt.




\section{Từ}

Khái niệm từ, mặc dù nghe qua rất thông dụng, dễ hiểu, nhưng định
nghĩa chính xác thế nào là từ không đơn giản. Từ trước đến nay đã có
nhiều định nghĩa về từ được đưa ra. Các định nghĩa đều đúng, tuy nhưng
không hoàn chỉnh. Viện sĩ L. V. Sherba thừa nhận rằng: ``Trong thực
tế, từ là gì? Thiết nghĩ rằng trong các ngôn ngữ khác nhau, từ sẽ khác
nhau. Do đó, tất sẽ không có khái niệm từ nói chung''\footnote{Nguyễn
  Kim Thản, {\em Nghiên cứu ngữ pháp tiếng Việt}. NXB GD, 1997. Trang 28}.
Chính vì tính đa dạng và phức tạp của từ mà một số nhà ngôn ngữ học
chối bỏ khái niệm từ, hoặc né tránh định nghĩa từ một cách chính
thức. Nhà ngôn ngữ học Ferdinand de Saussure đã nhận xét: ``\ldots{}
Ngôn ngữ có tính chất kỳ lạ và đáng kinh ngạc là không có những thực
thể thoạt nhìn có thể thấy ngay được, thế nhưng người ta vẫn biết chắc
là nó tồn tại, và chính sự giao lưu giữa những thực thể đó đã làm
thành ngôn ngữ. Trong số những thực thể đó có cái mà ngôn ngữ học vẫn
gọi là từ.''. Theo ông thì ``\ldots{} Từ là một đơn vị luôn luôn ám ảnh
toàn bộ tư tưởng chúng ta như một cái gì đó trọng tâm trong toàn bộ cơ
cấu ngôn ngữ, mặc dù khái niệm này khó định nghĩa''.


\subsection{Định nghĩa từ}

Thời Hy Lạp cổ đại, trường phái ngôn ngữ Alexandri đã định nghĩa: ``\textit{Từ
là đơn vị nhỏ nhất trong chuỗi lời nói}''. Ngoài ra A. Meillet trong
\textit{Ngôn ngữ học lịch sử và ngôn ngữ học đại cương} đã định nghĩa: ``\textit{Từ
là kết quả của sự kết hợp một ý nghĩa nhất định với một tổ hợp các âm
tố nhất định, có thể có một công dụng ngữ pháp nhất định}''.

Theo E. Sapir thì ``\textit{Từ là một đoạn nhỏ nhất có ý nghĩa, hoàn toàn có
khả năng độc lập và bản thân có thể làm thành câu tối giản}''. 

Theo L. Bloomfield thì từ là ``\textit{một hình thái tự do nhất}''.

Theo B. Golovin thì từ là ``\textit{đơn vị nhỏ nhất có ý nghĩa của ngôn ngữ,
được vận dụng độc lập, tái hiện tự do trong lời nói để xây dựng nên
câu}''.  

Theo Solncev thì ``\textit{Từ là đơn vị ngôn ngữ có tính hai mặt: âm và
nghĩa. Từ có khả năng độc lập về cú pháp khi sử dụng trong lời}''. 

Theo B. Trơ-nơ-ka thì ``\textit{Từ là đơn vị nhỏ nhất có ý nghĩa, được cấu tạo
bằng âm vị và có khả năng thay đổi vị trí và thay thế lẫn nhau trong
câu}''. 

Theo Lục Chí Vỹ thì ``\textit{Từ là đơn vị nhỏ nhất có thể vận dụng tự do
trong câu}''. 
Theo một số tác giả khác của Trung Quốc thì ``\textit{Từ là đơn vị từ vựng, là
đơn vị vật liệu kiến trúc của ngôn ngữ, và cũng là đơn vị nhỏ nhất có
khả năng vận dụng tư do trong lời nói}''. 

Theo V. G. Admoni thì ``\textit{Từ là đơn vị ngữ pháp, do hình vị cấu tạo nên,
dùng để biểu thị đối tượng, quá trình, tính chất và những mối quan hệ
trong hiện thực, có tính đặc thù rõ rệt và có khả năng kiến lập nhiều
mối quan hệ đa dạng với nhau}''. 

Theo R. A. Bunđagôp thì ``\textit{Từ là đơn vị nhỏ nhất và độc lập, có hình
thức vật chất (vỏ âm thanh và hình thức) và có nghĩa, có tính chất
biện chứng và lịch sử}''.

Đối với tiếng Việt, cũng có một số định nghĩa từ được đưa ra. Theo
M. B. Émeneau thì ``\textit{Từ bao giờ cũng tự do về mặt âm vị học, nghĩa là
có thể miêu tả bằng những danh từ của sự phân phối các âm vị và bằng
những thanh điệu}''\footnote{Nguyễn Thiện Giáp. {\em Từ và nhận diện từ
  tiếng Việt}. NXB GD, Hà Nội 1996. Trang 17}. Émeneau đã dựa trên mặt
ngữ âm để định nghĩa từ, xem mỗi từ trước hết là những âm tiết. Với
quan niệm như vậy chủ yếu dựa vào tính hoàn chỉnh về mặt âm thanh và
trong thực tế thì người Việt luôn có khuynh hướng mong đợi mỗi tiếng
như vậy sẽ mang một nghĩa nào đó và coi đó như ``từ''.

Theo Trương Văn Trình và Nguyễn Hiến Lê thì ``\textit{Từ là âm có nghĩa, dùng
trong ngôn ngữ để diễn tả một ý đơn giản nhất, nghĩa là ý không thể
phân tích ra được}''. Định nghĩa này chủ yếu dựa vào tính nhất thể của
nghĩa, nghĩa là mỗi từ có một nghĩa tối giản nào đó, và nghĩa của từ
có tính võ đoán và tính thành ngữ.

Lê Văn Lý cho rằng từ tiếng Việt ``\textit{là một tín hiệu ngữ âm có thể cấu
tạo bằng một âm vị hay sự kết hợp với âm vị, mà sự phát âm chỉ tiến
hành trong một lần, hoặc là một âm tiết mà chữ viết biểu thị bằng một
đơn vị tách rời và có một ý nghĩa hiểu được}''\footnote{Nguyễn
  Kim Thản, {\em Nghiên cứu ngữ pháp tiếng Việt}. NXB GD, 1997. Trang
  30}. Định nghĩa này dựa vào cả ba mặt: ngữ âm, chữ viết và ý
nghĩa. Tuy nhiên định nghĩa này mâu thuẫn với định nghĩa từ ghép của
chính tác giả, vì tác giả định nghĩa từ ghép dựa trên chức năng ngữ
pháp và gồm nhiều âm tiết.

Theo Phan Khôi thì ``\textit{Từ là một lời để tỏ ra một khái niệm trong khi
nói}''. Theo Nguyễn Lân thì ``\textit{Từ là những tiếng có nghĩa, tức là mỗi khi
nghe thấy, trong óc chúng ta đều có một khái niệm}''. Nếu xem từ tương
đương với khái niệm thì những từ hình thái như à, ư, nhỉ, nhé~\ldots{}
hay những hư từ như cũng, với, bởi~\ldots{} sẽ mang khái niệm gì? Trên
thực tế, từ và khái niệm không tương ứng 1-1 với nhau. Có những khái
niệm có thể biểu thị bằng nhiều từ.

Theo Nguyễn Kim Thản thì ``\textit{Từ là đơn vị cơ bản của ngôn ngữ, có thể
tách khỏi các đơn vị khác của lời nói để vận dụng một cách độc lập và
là một khối hoàn chỉnh về mặt ý nghĩa (từ vựng hay ngữ pháp) và cấu
tạo}''. Quan niệm của ông về ``đơn vị cơ bản'' là những đơn vị có số
lượng hữu hạn để thông báo, trao đổi tư tưởng cho nhau. Đơn vị này
phải có nghĩa, và khi sử dụng, người sử dụng phải có ý thức về
nó. Chính vì vậy mà đơn vị cơ bản này không thể là câu (vì số lượng
câu là vô hạn) và cũng không thể là âm tiết (vì nhiều âm tiết không có
nghĩa và khi sử dụng, người sử dụng không ý thức về nó). Vậy đơn vị cơ
bản là cái gì đó nhỏ hơn câu và lớn hơn âm tiết.

Theo Hồ Lê thì ``\textit{Từ là đơn vị ngữ ngôn có chức năng định danh phi liên
kết hiện thực, hoặc chức năng mô phỏng tiếng động, có khả năng kết hợp
tự do, có tính vững chắc về cấu tạo và tính nhất thể về ý
nghĩa}''. Theo ông, từ khác với âm tiết chủ yếu về mặt ý nghĩa. Từ có
ý nghĩa ngữ ngôn, còn âm tiết thì chỉ có ý nghĩa tiền ngữ ngôn. Từ
khác từ tố ở khả năng kết hợp. Từ có khả năng kết hợp tự do trong lời
nói, còn từ tố thì chỉ có khả năng kết hợp hạn chế. Từ khác với cụm từ
tự do bởi tính vững chắc về cấu tạo, tính nhất thể về ý nghĩa và bởi
chức năng định danh phi liên kết hiện thực. Từ khác cụm từ cố định
(thành ngữ, ngạn ngữ) chủ yếu bởi chức năng định danh phi liên kết
hiện thực của nó.

Đái Xuân Ninh chủ trương không định nghĩa từ, vì ``từ trước đến nay,
trong ngôn ngữ học đại cương cũng như trong tiếng nói cụ thể như tiếng
Việt, chưa có một định nghĩa nào thỏa đáng cả''. Theo ông thì ``đứng
về mặt chức năng và cấu trúc của ngôn ngữ, chỉ cần xác định đơn vị từ
và mối quan hệ của nó với các đơn vị khác trong tiếng nói''. Ông cho
rằng ta có thể nhận diện từ một cách khái quát như sau: ``\textit{Từ
  là đơn vị cơ bản của cấu trúc ngôn ngữ ở giữa hình vị và cụm từ. Nó
  được cấu tạo bằng một hay nhiều đơn vị ở hàng ngay sau nó tức là
  hình vị và lập thành một khối hoàn chỉnh}''.


Nguyễn Tài Cẩn, tuy không định nghĩa trực tiếp từ tiếng Việt, nhưng
ông đã chứng minh những tính chất đặc biệt của ``tiếng'', một đơn vị
mà ông coi chính là hình vị và có tính năng rất gần với ``từ'', nó
cũng chính là ``từ đơn'' và là thành tố trực tiếp để tạo nên ``từ
ghép''. Theo ông, mọi đặc thù về từ pháp của tiếng Việt bắt nguồn từ
tính đơn lập của tiếng Việt mà thể hiện rõ nét nhất là qua một đơn vị
đặc biệt, đó chính là tiếng. Quan điểm này cũng được Cao Xuân Hạo đồng
tình. 

Kế thừa quan điểm coi tiếng gần trùng với từ. Nguyễn Thiện Giáp đã
phát triển tư tưởng này lên đến mực cực đoan là coi tiếng trong tiếng
Việt chính là từ trong các ngôn ngữ Ấn-Âu. Theo ông ``\textit{Nếu quan
  niệm từ không chỉ là đơn vị ngôn ngữ học mà còn là đơn vị tâm
  lý-ngôn ngữ học, nếu chú ý đến tính nhiều mặt của từ và đặc điểm của
  từ trong từng ngôn ngữ, nếu nhận diện từ căn cứ vào những quan hệ
  đối lập trong nội bộ từng ngôn ngữ thì cái đơn vị gọi là ``tiếng''
  của Việt ngữ có đủ tư cách để được gọi là ``từ''}''. Như vậy Nguyễn
Thiện Giáp đã không sử dụng đến khái niệm hình vị trong tiếng Việt
(đơn vị dùng để cấu tạo từ trong các ngôn ngữ Ấn-Âu). Trong quan niệm
về từ của ông, ông chủ yếu dựa trên các tiêu chí nhận diện thuộc về
hình thức mà không nhấn mạnh tiêu chí về ngữ nghĩa và khả năng độc lập
về ngữ pháp.

\subsection{Đặc điểm của từ}

Từ các định nghĩa trên, có thể rút ra các đặc điểm chính của từ nói
chung như sau:
\begin{itemize}
\item Về hình thức, từ phải là một khối về cấu tạo (chính tả, ngữ
  âm~\ldots{}).
\item Về nội dung, từ phải có ý nghĩa hoàn chỉnh.
\item Về khả năng, từ có khả năng hoạt động tự do và độc lập về cú
  pháp.
\end{itemize}

Đối với từ tiếng Việt, ta có thể rút ra những đặc điểm của từ tiếng
Việt so với các ngôn ngữ thuộc loại hình khác.
Tiếng Việt là một ngôn ngữ đơn lập với các đặc điểm chính như sau:
\begin{itemize}
\item Trong hoạt động ngôn ngữ, từ không biến đổi hình thái. Ý nghĩa
  ngữ pháp nằm ở ngoài từ. 
\item Phương thức ngữ pháp chủ yếu là trật tự từ và từ hư.
\item Tồn tại một đơn vị đặc biệt là hình tiết mà vỏ ngữ âm của nó
  trùng khít với âm tiết. Đơn vị đó còn được gọi là tiếng.
\item Không có hiện tượng cấu tạo từ bằng cách ghép thêm phụ tố vào
  gốc từ.
\end{itemize}

%% Khái niệm ``đơn vị cơ bản'' trong ngôn ngữ phải giống như trong các
%% ngành khác. Đó là những đơn vị mang đầy đủ các đòi hỏi về những tính
%% chất phải có trong khái niệm ``cơ bản''. Chính vì vậy, trong ngôn ngữ
%% học, khi nói đến ``đơn vị cơ bản'' thì số lượng đơn vị ấy phải không
%% được quá nhiều mà của không được quá ít. Chiều dài của ``đơn vị cơ
%% bản'' cũng không thể quá dài hoặc quá ngắn. Tuy nhiên đây chỉ là điều
%% kiện ban đầu để xem xét đơn vị cơ bản. Đơn vị cơ bản cần phải thoả mãn
%% nhiều điều kiện khác như kết cấu, nội dung~\ldots{}

%% Xét về hình thức đơn vị ``tiếng'' trong tiếng Việt, ta thấy đơn vị này
%% thoả mãn các điều kiện ban đầu của một đơn vị cơ bản về số lượng cũng
%% như chiều dài. Số lượng tiếng thường dùng khoảng 8.200 tiếng, tối đa
%% khoảng 40.000 tiếng. Chiều dài trung bình của một tiếng vào khoảng 4-5
%% chữ cái, tối đa khoảng 7 chữ cái.

\subsection{Các quan niệm về hình vị và từ trong tiếng Việt}

Đối với từ trong tiếng Việt, đến nay có một số quan điểm như sau:
\begin{itemize}
\item Coi mọi tiếng đều là từ (Nguyễn Thiện Giáp). Điều này thuận tiện
  trong xử lý nhưng không đúng với tiêu chí ngôn ngữ học đại cương vì
  có nhiều tiếng không có nghĩa, như ``phê'' trong ``cà phê'', ``bù''
  trong ``bù nhìn''~\ldots{}
\item Coi tiếng chưa hẳn là từ (đa số các nhà Việt ngữ học). Trong số
  này chia thành ba nhóm sau:
  \begin{itemize}
  \item Xem tiếng là hình vị. Quan niệm có thể chấp nhận được nếu coi
    hình vị là hình vị tiếng Việt (gồm tha hình vị và á hình vị)
  \item Xem tiếng lớn hơn hình vị (Trần Ngọc Thêm, Lưu Văn
    Lang~\ldots{}) cho là tiếng có những hình vị (khuôn vần).
  \item Xem tiếng nhỏ hơn hoặc bằng hình vị. Đa số các tiếng đều là
  hình vị, ngoại trừ ``hấu'' trong ``dưa hấu'', ``bù'' trong ``bù
  nhìn''~\ldots{} vì những tiếng này không có nghĩa. Quan điểm này được
  nhiều người chấp nhận.
  \end{itemize}
\item Xem tiếng châu Âu (Anh, Pháp~\ldots{}) cái nào là từ thì trong
  tiếng Việt cái đó là từ. Quan điểm này chưa xét đến sự khác biệt về
  sự từ vựng hoá giữa hai ngôn ngữ do khác biệt về văn hoá.
\end{itemize}

Theo quan điểm ngôn ngữ học đại cương, từ được cấu tạo bởi các hình
vị, và hình vị chính là các đơn vị có nghĩa nhỏ nhất. Vì vậy, từ trong
tiếng Việt cũng phải được cấu tạo bởi các hình vị nêu trên, nhưng có
điều khác là các hình vị thành phần ở đây không hoàn toàn giống khái
niệm hình vị của ngôn ngữ học đại cương, mà là ``hình vị tiếng Việt''
hay còn gọi là ``hình tiết'' (hình vị + âm tiết) hay ``tiếng'' (vì chỉ
tiếng Việt mới có đơn vị tiếng đặc biệt như vậy).



\section{Từ láy}

Từ láy là từ mà các thành tố kết hợp với nhau chủ yếu là theo quan hệ
ngữ âm. Số lượng từ láy trong tiếng Việt rất lớn, khoảng 4000 từ. Quan
hệ ngữ âm trong từ láy thể hiện ở hai mặt: 
\begin{itemize}
\item Tương ứng về yếu tố siêu đoạn tính (thanh điệu)
\item Tương ứng về yếu tố âm đoạn tính (phụ âm đầu, vần và các yếu tố
  trong vần)
\end{itemize}



Các thành tố của từ láy thường phải có thanh thuộc cùng một âm vực:
hoặc thuộc âm vực cao (ngang, hỏi, sắc), hoặc thuộc âm vực thấp
(huyền, ngã, nặng)\footnote{Trong tiếng Việt hiện đại, thanh ngã thuộc
  âm vực cao, thanh hỏi thuộc âm vực thấp. Tuy nhiên về mặt lịch sử,
  thanh hỏi trước kia thuộc âm vực cao còn thanh ngã lại thuộc âm vực
  thấp (A.G. Haudricourt, 1954)}

Các từ láy có nhiều kiểu, bao gồm láy toàn bộ và láy bộ phận (láy vần,
láy phụ âm đầu). Luật hài thanh của mỗi kiểu láy có đặc điểm riêng:
\begin{itemize}
\item Trong các từ láy toàn bộ, âm tiết đầu thường là một trong các
  thanh bằng (1, 2) còn âm tiết thứ hai thường là một trong các thanh
  trắc (3, 4, 5, 6) cùng âm vực với nó.
\item Trong các từ điệp vận, thường có xu hướng thống nhất các thanh
  điệu ở cả hai âm tiết. Theo thống kê của Nguyễn Thiện Giáp, có 81\%
  số từ láy vần có thanh điệu hai âm tiết giống nhau hoàn toàn. Trong
  một số trường hợp, sự kết hợp của thanh điệu trong từ láy không theo
  đúng luật hài thanh (như \textit{khe khẽ, se sẽ, xốp xộp~\ldots}) có
  thể giải thích bằng sự thay đổi lịch sử của thanh ngã từ âm vực thấp
  lên âm vực cao, kéo theo sự thay đổi của các thanh điệu khác kết hợp
  với nó, hoặc do quan hệ với cơ chế láy ba.
\item Trong các từ láy phụ âm đầu, thanh điệu của hai âm tiết không
  bắt buộc phải giống nhau, chỉ cần hai thanh điệu ở hai âm tiết cùng
  âm vực là được.
\end{itemize}

Sự phân bố thanh điệu trong các từ láy tiếng Việt tuân theo luật
phù-trầm. Luật hài hoà thanh điệu này bị chế định rõ rệt trong kiểu
láy vần do mối quan hệ chặt chẽ giữa vần và thanh điệu.

\section{Từ ghép}

XXX

\section{Chính tả tiếng Việt}


\subsection{Tổng quan về chữ viết tiếng Việt}


% Nổ một tí về chữ quốc ngữ

Chữ viết là một trong những phương tiện giao tiếp hiệu quả. Chữ viết
cho phép vượt qua những giới hạn về không gian và thời gian của tiếng
nói. Nhờ đặc điểm này, chữ viết được sử dụng rộng rãi trong nhiều lĩnh
vực khác nhau của đời sống.

Có nhiều hệ thống chữ viết khác nhau được sử dụng trên thế giới, nhưng
nhìn chung có thể phân thành hai loại chữ viết sau:
\begin{description}
\item[Chữ viết ghi ý] Đây là loại chữ viết biểu hiện từ bằng một ký
  hiệu duy nhất, không liên quan gì đến những âm thanh cấu tạo nên
  từ. Ký hiệu này liên quan với cả từ và do đó cũng gián tiếp có quan
  hệ với ý niệm mà từ đó biểu hiện. Loại này bao gồm chữ Trung Quốc, chữ Ai
  Cập~\ldots{}

  Vì các ký hiệu chữ viết không phản ánh mặt âm thanh và hình thức ngữ
  pháp của từ mà phản ánh mặt ý nghĩa, nên trong tiếng Trung Quốc
  những từ đồng âm được biểu hiện bằng những chữ hoàn toàn khác nhau.

\item[Chữ viết ghi âm] Đây là loại chữ viết nhằm tái hiện chuỗi âm
  thanh nối tiếp nhau trong từ. Các hệ thống chữ viết ngữ âm học có
  thể ghi âm tiết hay âm tố.
  \begin{description}
  \item[Chữ ghi âm tiết] Mỗi ký hiệu ghi một âm tiết. Dẫn chứng cho
  loại chữ viết này là hệ thống chữ Nhật Hiragana và Katakana.

  \item[Chữ ghi âm tố] Mỗi ký hiệu ghi một âm tố (hay âm vị). Ví dụ
  như chữ Anh, chữ Pháp, chữ Nga~\ldots{}

  \end{description}
\end{description}

Hệ thống chữ viết được sử dụng hiện nay của nước ta là chữ quốc
ngữ. Nước ta trước đây vẫn dùng chữ Hán và chữ Nôm. Chữ quốc ngữ được
hình thành từ thời Pháp đô hộ nước ta, được người Pháp sử dụng
trong các văn tự chính thức và càng ngày càng được sử dụng rộng rãi.

Chữ quốc ngữ ra đời cách nay khoảng ba thế kỷ. Đó là công trình của
một nhóm các cố đạo người châu Âu cộng tác cùng một số người
Việt. Người để lại nhiều tác phẩm có giá trị trong giai đoạn đầu của
chữ quốc ngữ là Alexandre de Rhodes.

% Đặc điểm chữ quốc ngữ

Chữ quốc ngữ là một lối chữ ghi âm, dùng chữ cái Latin. Nó dùng những
ký hiệu (tức là những con chữ, mượn từ chữ cái Latin, có thêm các dấu
phụ) để ghi lại những âm vị, âm tố và các thanh điệu tiếng Việt. Chữ
quốc ngữ về căn bản khác với chữ Hán và chữ Nôm. Chữ Hán là lối chữ
ghi ý. Chữ Nôm của chúng ta ngày xưa về căn bản cũng là lối chữ ghi ý,
tuy có nhiều thành phần ghi âm.

So với chữ Nôm, chữ quốc ngữ có tiến bộ rất lớn vì nó là chữ ghi âm
rất giản tiện, sử dụng vài chục ký hiệu giản tiện là có thể biểu diễn
được hệ thống âm thanh tiếng Việt.

So với các hệ thống chữ ghi âm khác như chữ Anh, chữ Pháp thì chữ quốc
ngữ là một hệ thống ``chữ viết trẻ'', mới được dùng phổ biến hơn
một thế kỷ nay, nên giữa chữ và âm tương đối có sự phù hợp.

Nguyên tắc chính tả cơ bản của chữ quốc ngữ là nguyên tắc ngữ âm học,
có nghĩa là ``phát âm thế nào thì viết thế ấy'', nên có sự tương ứng
khá lớn giữa chữ viết và phát âm.




\subsection{Chính tả tiếng Việt}


Nói ngắn gọn, chính tả là toàn bộ những tiêu chuẩn và những qui luật
thực hành chữ viết, bao gồm:
\begin{enumerate}
\item Những luật dùng các con chữ của bảng chữ cái để viết các từ.
\item Luật viết các từ độc lập với những chữ cái khi viết chúng.

  Ví dụ: Cách dùng các dấu câu, cách viết hoa, tên người, tên đất~\ldots{} 
\end{enumerate}

Chuẩn mực của cách viết thường tuân theo những nguyên tắc khác nhau.

Đối với những luật chính tả liên quan đến việc sử dụng các con
chữ của bảng chữ cái ghi âm, có thể kể đến các nguyên tắc cơ bản sau
đây:

\begin{description}
\item[Nguyên tắc âm vị học] Mỗi âm vị được thể hiện bằng một
  chữ cái, không phụ thuộc vào vị trí của nó trong các từ và tổ hợp
  từ. 
\item[Nguyên tắc ngữ âm học] Chữ cái phản ánh phát âm của âm vị ở
  những vị trí hay bối cảnh khác nhau.
\item[Nguyên tắc từ nguyên] Nguyên tắc viết theo lịch sử, truyền
  thống. Phản ánh trên chữ viết không phải là trạng thái hiện tại mà
  là trạng thái quá khứ của hệ thống âm thanh. 
\end{description}

Trong bất kỳ một hệ thống chữ viết nào cũng có thể thấy sự kết hợp các
nguyên tắc khác nhau. Nhưng mỗi hệ thống chữ viết có những nguyên tắc
chủ yếu. Chữ quốc ngữ được xây dựng chủ yếu trên nguyên tắc âm vị học
và ngữ âm học. Ngược lại, chữ Pháp và chữ Anh chủ yếu dùng nguyên tắc
từ nguyên, viết theo truyền thống lịch sử.

% Cấu trúc âm tiết:
Âm tiết trong tiếng Việt có 5 thành phần, đó là thanh điệu, âm đầu, âm
đệm, âm chính và âm cuối.

Âm đầu các âm vị phụ âm đảm nhiệm. Các âm tiết mà có chữ trên chữ viết
không ghi phụ âm đầu có thể có âm đầu là âm tắt thanh hầu \textipa{/P/}.

Âm đệm do các âm vị bán nguyên âm \textipa{/-u-/} đảm nhiệm.

Âm chính do các âm vị nguyêm âm đảm nhiệm như trong bảng~\ref{tab:nguyenam}.

%\begin{savenotes}
  \begin{table}[htbp]
    \centering

    \begin{tabular}{cc|cc}
      Âm vị&Chữ cái&Âm vị&Chữ cái\\
      \textipa{/i/}&i,y&\textipa{/o/}&ô,ôô\\
      \textipa{/e/}&ê&\textipa{/O/}&o,oo\\
      \textipa{/E/}&e,a&\textipa{/\v{7}/}&â\\
      \textipa{/W/}&ư&\textipa{/\v{a}/}&a,ă\\
      \textipa{/7/}&ơ&\textipa{/ie/}&iê,ia,yê,y\\
      \textipa{/a/}&a&\textipa{/uo/}&uô,ua\\
      \textipa{/u/}&u&\textipa{/W7/}&ươ,ưa\\
    \end{tabular}
    
    \caption{Bảng nguyên âm}
    \label{tab:nguyenam}
  \end{table}
%\end{savenotes}

Âm cuối do các âm vị phụ âm bán nguyên âm đảm nhiệm như trong
bảng~\ref{tab:amcuoi}. 

\begin{table}[htbp]
  \centering

  \begin{tabular}{cc|cc}
    \multicolumn{2}{c|}{Phụ âm cuối}&\multicolumn{2}{c}{Bán nguyên âm cuối}\\
    Âm vị&Chữ cái&Âm vị&Chữ cái\\
    \textipa{/-p/}&p&\textipa{/-u/}&u,o\\
    \textipa{/-t/}&t&\textipa{/-i/}&i,y\\
    \textipa{/-k/}&c,ch\\
    \textipa{/-m/}&m\\
    \textipa{/-n/}&n\\
    \textipa{/-N/}&ng,nh\\
  \end{tabular}
    
  \caption{Bảng phụ âm và bán nguyên âm cuối}
  \label{tab:amcuoi}
\end{table}

Trên chữ viết, các âm vị âm đầu được thể hiện như trong bảng~\ref{tab:phuamdau}

%\begin{savenotes}
  \begin{table}[htbp]
    \centering
  \begin{minipage}[htbp]{0.6\textwidth}
    \def\thefootnote{\alph{mpfootnote}}
    \centering

    \begin{tabular}{cc|cc}
      Âm vị&Chữ cái&Âm vị&Chữ cái\\
      \textipa{/b/}&b&\textipa{/m/}&m\\
      \textipa{/f/}&ph&\textipa{/v/}&v\\
      \textipa{/t\super{h}/}&th&\textipa{/t/}&t\\
      \textipa{/d/}&đ&\textipa{/n/}&n\\
      \textipa{/s/}&x&\textipa{/z/}&d,gi\footnote{Dựa vào nguyên tắc từ nguyên để phân biệt}\\
      \textipa{/l/}&l&\textipa{/\:t/}&tr\\
      \textipa{/\:s/}&s&\textipa{/\:z/}&r\\
      \textipa{/c/}&ch&\textipa{/\textltailn/}&nh\\
      \textipa{/k/}&
      q\footnote{Dùng khi đứng trước bán nguyên âm \textipa{/-u-/}}, 
      k\footnote{Dùng khi đứng trước các nguyên âm \textipa{/i,e,E,ie/}},
      c&
      \textipa{/N/}&ngh\footnotemark, ng\\
      \textipa{/x/}&kh&\textipa{/G/}&gh\footnotemark, g\\
      \textipa{/h/}&h&\textipa{/P/}&khuyết\\
    \end{tabular}
    
    \caption{Bảng phụ âm đầu}
    \label{tab:phuamdau}

  \end{minipage}
  \end{table}
%\end{savenotes}

Một số âm như k và  q, gh và g, ngh và ng là cùng âm vị. Tuy nhiên, do
khi hình thành chữ quốc ngữ, ngữ âm tiếng Việt chưa được nghiên cứu
đầy đủ, nên các giáo sĩ đã phải mượn nhiều con chữ ghép trong chữ Bồ
Đào Nha, Hi Lạp, Pháp, Ý~\ldots{} dẫn đến sự không đồng nhất khi biểu
diễn âm vị.

Hệ thống âm chính tiếng Việt dựa trên cách phát âm Hà Nội bao gồm 9
nguyên âm dài, 2 nguyên âm ngắn, 3 nguyên âm đôi. Tóm gọn các cách
biểu diễn nguyên âm chính gồm: i, y, ê, e, a, ư, ơ, a, u, ô, o, â, ă,
iê, ia, yê, y, uô, y, uô, ươ, ưa.

Các phụ âm cuối được ghi bằng ``ch'' khi đứng sau các nguyên âm i, y,
ê, e, a. Ví dụ: {\em minh, mênh, manh}. Trong các trường hợp khác lại
được ghi bằng ``ng''. Ví dụ: {\em mang, vâng, hồng, xuống}.

Các bán nguyên âm cuối /-u/ ghi bằng ``o'' khi đứng sau các nguyên âm đơn
dài, ở bậc thanh lượng lớn như e, a. Các viết này biểu diễn sự biến
dạng của các bán âm sau các mở rộng. Trong các trường hợp còn lại, bán
nguyên âm này được ghi bằng ``u''.

Các bán nguyên âm cuối /-i/ được ghi bằng ``y'' khi đứng sau các
nguyên âm ngắn ă, a, â. Trong các trường hợp khác nó được ghi bằng
``i''.

Tóm lại, các âm vị cuối được thể hiện bằng những chữ cái: p, t, c, ch,
m, n, ng, nh, u, o, i, y.

Tiếng Việt có sáu thanh điệu: sắc, huyền, ngã, hỏi, nặng và thanh không dấu. 

Về việc bỏ dấu, có ba nguyên tắc bỏ dấu sau:
\begin{description}
\item[Nguyên tắc bỏ dấu khoa học] Dấu thanh được đặt ở âm chính của
  vần, tức là đặt trên hoặc dưới nguyên âm có vai trò quyết định âm
  sắc chủ yếu của âm tiết.
\item[Nguyên tắc thẩm mỹ] (nguyên tắc thứ yếu) Dấu thanh được đặt ở vị
  tri cân đối trong âm tiết. Nguyên tắc này trước đây hay dùng nhưng
  nay trong một số trường hợp nếu đặt dấu thanh sai sẽ làm cho phát âm
  không đúng và hiểu sai nghĩa từ.
\item[Nguyên tắc thực dụng] Dấu thanh thường được đặt vào một con chữ
  nguyên âm chứ không đặt ở giữa hai con chữ, để tiện việc in ấn.
  \begin{itemize}
  \item Nếu âm chính là một nguyên âm đơn thì dấu thanh luôn luôn được
  ghi ở trên hoặc ở dưới âm chính.
  \item Nếu âm chính là một nguyên âm đôi thì tùy trường hợp có thể bỏ
  đấu thanh ở yếu tố thứ nhất hoặc yếu tố thứ hai của âm chính.
  \end{itemize}
\end{description}

XXX% \subsection{Những qui định về chính tả tiếng Việt}


\subsection{Lỗi chính tả}

% Lỗi chính tả là gì?

Theo~\cite{LoiChinhTa} thì:
\begin{verse}
  Chữ viết là hệ thống ký hiệu bằng đường nét đặt ra để ghi tiếng nói
  và có những qui tắc, qui định riêng. Muốn viết đúng chính tả tiếng
  Việt, ta phải tuân theo những qui định, qui tắc đã được xác lập.

  Chính tả là cách viết chữ được xem là chuẩn, tức là viết đúng âm
  đầu, đúng vần, đúng dấu (thanh), đúng quy định về viết hoa, viết
  tắt, viết thuật ngữ.
\end{verse}

Các lỗi chính tả thường rơi vào loại lỗi do phát âm sai dẫn đến viết
sai (lỗi hỏi-ngã, lỗi sai âm đầu, sai âm chính, sai âm cuối). Ngoài ra
còn các loại lỗi khác như viết hoa không đúng qui cách, viết tên
riêng, thuật ngữ, tên tiếng nước ngoài không đúng qui cách.

%% Tiếng Việt có sáu thanh điệu, nhưng hầu hết mọi người không phân biệt
%% hai thanh hỏi và ngã. Loại lỗi này rất phổ biến, kể cả ở những người
%% có trình độ văn hoá cao. Nguyên nhân là do các phương ngữ Trung và Nam
%% Bộ không có thanh ngã. Ngoài ra số tiếng mang hai thanh này khá lớn
%% (khoảng 1900 tiếng mang thanh hỏi và 900 tiếng mang thanh ngã)

%% Về âm đầu, các âm sau thường bị lẫn lộn: C/K, G/Gh, Ng/Ngh,
%% Ch/Tr, S/X, V/D/Gi/R, W/Hw/Ngw/Qu.

%% Về âm chính thường lẫn lộn các âm sau: ai/ay/ây,
%%   ao/au/âu, ăm/âm, ăp/âp, iu/iêu/êu, im/iêm/em, ip/iêp/êp/ep,
%%   oi/ôi/ơi, om/ôm/ơm, op/ôp/ơp, ong/ông, oc/ôc, ui/uôi, um/uôm, up/(uôp),
%%   ưi/ươi, ưu/ươu, ưm/ươm, (ưp)/ươp.

%% Về âm cuối thường lẫn lộn chữ ghi các âm cuối trong các vần   sau:
%%   an/ang, at/ac, ăn/ăng, ăt/ăc, ân/âng, ât/âc, en/eng, et/ec, ên/ênh,
%%   êt/êch, in/inh, it/ich, iên/iêng, iêt/iêc, ơn/(ơng), ơt/(ơc),
%%   un/ung, ut/uc, uôn/uông, uôt/uôc, ưn/ưng, ưt/ưc, ươn/ương, ươt/ươc.

%% Sai quy cách viết hoa do chưa thống nhất quy cách viết hoa (hoặc thống
%% nhất quá trễ)


%% XXX

\chapter{Cơ sở tin học}
\label{cha:math}
\minitoc

% typographic errors

%% Lỗi gõ sai được xử lý bằng thuật toán soundex~\cite{soundex}. Ý tưởng
%% của thuật toán này dựa trên các nghiên cứu về nguyên nhân gây ra
%% lỗi. Theo~\cite{soundex}, có bốn nguyên nhân gây ra lỗi loại này:
%% \begin{itemize}
%% \item Chèn một ký tự đơn.
%% \item Xoá một ký tự đơn.
%% \item Thay một ký tự bằng một ký tự khác.
%% \item Hoán đổi vị trí hay ký tự kề nhau.
%% \end{itemize}
%% Thuật toán này

\section{Bắt lỗi chính tả}

Trình bắt lỗi chính tả có thể được đánh giá theo nhiều cách khác
nhau. Nhưng chủ yếu vẫn được phân loại từ quan điểm người dùng: khả
năng phát hiện lỗi sai, và khả năng đề nghị những từ thay thế cho lỗi
sai đó.

\subsection{Phát hiện lỗi chính tả}

Giải pháp đơn giản để phát hiện lỗi chính tả là dùng một cấu trúc dữ
liệu để lưu tất cả các từ đã biết (được lưu trong từ điển). Nếu từ
không có trong từ điển nghĩa là từ đó bị sai. Giải pháp này cần thêm
một số heuristic để tránh không xem các con số, ngày tháng~\ldots{} là
lỗi sai.

Đối với trình bắt lỗi chính tả truyền thống thì từ điển là một phần
rất quan trọng. Từ điển có thể được lưu theo các dạng
cấu trúc dữ liệu như bảng băm hoặc cấu trúc dữ liệu dạng cây có thể
được sử dụng~\cite{McIlroy,Peterson}

Với những lỗi sai dạng lỗi từ vựng, ta phải dùng một số phương pháp
khác phức tạp hơn để phát hiện (chi tiết trong
phần~\ref{sec:context-spelling}). 

\subsection{Các sai lầm của trình bắt lỗi chính tả}

Khi bắt lỗi chính tả, trình bắt lỗi không tránh khỏi các sai lầm. Có
thể phân ra làm hai loại sai lầm: sai lầm tích cực\footnote{false
  positive} và sai lầm tiêu cực\footnote{false negative}.

Sai lầm tích cực xảy ra khi trình bắt lỗi báo lỗi ở những từ hoàn toàn
không sai chính tả. Sai lầm tiêu cực xảy ra khi trình bắt lỗi bỏ qua
những từ bị sai chính tả. Nói cách khác, trình bắt lỗi cho rằng những
từ sai chính tả này không sai. Sai lầm tích cực có thể tránh được nhờ
tăng kích thước từ điển. Tuy nhiên đây không phải là giải pháp hoàn
hảo. Việc tăng kích thước từ điển sẽ tốn kém (về bộ nhớ, CPU, cũng như
công sức bỏ ra để xây dựng từ điển). Hơn nữa, càng có nhiều
từ thì việc đề nghị các từ thay thế càng trở nên kém hiệu quả do bị
phân tán bởi những từ rất ít gặp, không thể tập trung vào những lỗi
phổ biến. 

Sai lầm tiêu cực có thể xem là lỗi không phát hiện được. Phần nhiều
những lỗi này thường đòi hỏi phải hiểu văn bản (ít nhất là một phần
văn bản) để có thể phát hiện lỗi. Những dạng lỗi từ vựng, lỗi cú pháp
thường rơi vào dạng này. Tuy nhiên vẫn có một số lỗi chính tả rơi vào
loại này. Những loại lỗi này được phát hiện nhờ những chương trình bắt
lỗi chính tả cảm ngữ cảnh (xem phần~\ref{sec:context-spelling}).

%~\cite{Golding95,Golding96,Golding99}

Trong hai loại sai lầm thì sai lầm tích cực thường gây khó chịu cho
người sử dụng, dễ gây tâm lý không tin tưởng vào trình bắt lỗi chính
tả. Ngược lại, sai lầm tiêu cực phản ánh tính hiệu quả của trình bắt
lỗi chính tả. Sai lầm tiêu cực càng nhiều thì trình bắt lỗi càng kém
hiệu quả.

\subsection{Vấn đề chữ hoa, chữ thường}

Vấn đề chữ hoa/chữ thường gây nhiều khó khăn cho trình bắt lỗi chính
tả. Trong từ điển, hầu hết các từ là chữ thường. Tuy nhiên cũng có chữ
hoa (tên riêng, từ viết tắt~\ldots{}). Các quy tắc chính tả về viết hoa
cũng khá phức tạp. Ngoài ra, đôi khi các chữ được viết hoa hoàn toàn
để nhấn mạnh, để làm tiêu đề~\ldots{}

Thuật toán để xử lý trường hợp chữ hoa, chữ thường có thể được mô tả
như sau:
\begin{algo}[Xử lý chữ hoa, chữ thường]
\begin{enumerate}
\item Đặt $w_t$ là chữ viết thường của $w$.
\item Đặt $c$ là kết quả tìm kiếm $w_t$.
\item Nếu không tìm được $c$, từ bị sai chính tả.
\item Nếu $c$ giống $w$, từ đúng.
\item Đặt $c_c$ là chữ thường, viết hoa chữ cái đầu tiên của $w$. Nếu
  $c$ giống $c_c$, từ đúng.
\item Đặt $c_u$ là chữ hoa của $w$. Nếu $c$ giống $c_u$, từ đúng.
\item Ngược lại, từ $w$ sai.
\end{enumerate}
\end{algo}



\section{Lập danh sách từ đề nghị}

Sau khi phát hiện ra từ bị sai chính tả, ta cần đưa ra một số từ ``gần
giống'' có khả năng thay thế từ bị sai chính tả. Trong trường hợp lý
tưởng, ta nên đưa ra {\em duy nhất một từ}, đó chính là từ đúng
chính tả, lẽ ra cần phải được dùng thay cho từ bị sai chính tả.

Tuy nhiên, việc tìm ra từ đúng của từ bị sai chính tả là một công việc
không dễ dàng, ngay cả với con người. Khi gặp một từ sai chính tả, ta
thường phải suy nghĩ nhiều, chọn ra một số từ có khả năng thay thế,
kiểm nghiệm xem từ nào là từ thích hợp nhất. Quá trình kiểm nghiệm xem
từ nào là thích hợp thường đòi hỏi phải hiểu về nội dung của văn bản
đang xem (đối với con người). Đối với máy tính, việc hiểu văn bản, đến
nay vẫn là một vấn đề khó. Tuy nhiên, máy tính cũng có khả năng tìm ra
kết quả đối với một số trường hợp lỗi thông dụng (chi tiết trong phần
\ref{sec:context-spelling}). Việc tìm ra chỉ một kết quả duy nhất đưa
đến một thuận lợi đáng kể. Bởi vì chỉ có một kết quả, không cần phải lựa
chọn, nên ta có thể tạo ra chương trình bắt lỗi chính tả (và sửa lỗi
chính tả) tự động. Việc tạo ra một chương trình bắt lỗi chính tả tự
động hoàn toàn mở ra một khả năng to lớn khi áp dụng vào thực tế, giúp
giảm đáng kể công sức của con người.

Trong trường hợp không thể đưa ra duy nhất một đề nghị, ta có thể đưa
ra một danh sách các từ ``có khả năng'' để người dùng chọn lựa. Yêu
cầu đặt ra là từ đúng phải nằm trong danh sách từ lựa chọn. Và tốt hơn
nữa là từ đúng nên được đặt trên cùng danh sách để gây sự chú ý của
người dùng (chi tiết trong phần \ref{sec:sort-candidates}). Để đảm
bảo từ đúng nằm trong danh sách, ta cần tìm hiểu nguyên nhân dẫn đến
lỗi, sau đó cố gắng phục hồi lỗi để tạo lại những từ có khả năng. Do
có nhiều nguyên nhân khác nhau dẫn đến lỗi chính tả, nên cũng có nhiều
cách khác nhau để phát sinh danh sách từ đề nghị.


\subsection{Lỗi phát âm sai}

Đối với các ngôn ngữ như tiếng Việt --- vốn ``nói sao viết vậy'', giải
pháp khá đơn giản. Ta có thể phân tích cấu trúc tiếng trong tiếng
Việt, sau đó dựa vào các cách phát âm giống nhau để tạo ra danh sách
các tiếng phát âm giống nhau. 

Đối với các ngôn ngữ như tiếng Anh --- cách viết không còn tương ứng
với cách đọc nữa, thì giải pháp sẽ phức tạp hơn. Cơ bản là ta cần một
cách nào đó để chuyển từ được viết thành một dạng phiên âm, sau đó áp
dụng như bình thường. Một số heuristic được đưa ra để giải quyết vấn
đề này. Thuật toán cơ bản là Soundex~\cite{knuth73}. Nhiều thuật toán
khác được đưa ra để cải tiến Soundex như Double
Metaphone\footnote{http://aspell.sourceforge.net/metaphone/}, 
Phonetex~\cite{phonetex}. Soundex cũng được cải tiến để áp dụng cho
các ngôn ngữ khác, như tiếng Thái~\cite{tsdx}. Nói chung, các kỹ thuật
này biến đổi về cơ bản thay thế các ký tự trong từ bằng như ký tự khác
chung hơn, với mục đích làm cho sau khi biến đổi, các từ có cách đọc
giống nhau sẽ trở nên giống nhau. Ví dụ như trong Soundex:
\begin{itemize}
\item Các ký tự ``aeiouhwy'' được thay bằng ``0''.
\item ``bpfv'' được thay bằng ``1''.
\item ``cgjkqsxz'' được thay bằng ``2''.
\item ``dt'' được thay bằng ``3''.
\item ``l'' được thay bằng ``4''.
\item ``mn'' được thay bằng ``5''.
\item ``r'' được thay bằng ``6''.
\end{itemize}
Cách thay thế khác nhau tùy vào từng thuật giải. Ngoài ra, các
thuật giải có thể giữ lại một số ký tự mà không thay thế.

\subsection{Lỗi nhập sai}

Lỗi nhập liệu xảy ra khi gõ không
đúng phím cần gõ trên bàn phím. Damerau~\cite{Damerau} xác định bốn thao
tác có thể gây ra lỗi như sau:
\begin{itemize}
\item Tráo đổi một cặp ký tự.
\item Xóa một ký tự đã có.
\item Chèn một ký tự lạ.
\item Thay một ký tự bằng một ký tự khác.
\end{itemize}

Damerau cho rằng 80\% các lỗi là do thực hiện thao tác trên  một lần
(một trong bốn thao tác trên).

Phân loại lỗi theo các thao tác trên dẫn đến một kỹ thuật sửa lỗi đơn
giản được dùng bởi~\cite{Petersonb}. Nếu phát hiện một từ bị sai
chính tả, ta lần lượt thực hiện lại những thao tác trên để phục hồi từ
bị sai chính tả. Những từ được phát sinh, nếu có trong từ điển, sẽ
được lưu vào danh sách những từ đề nghị. Kỹ thuật này thường được gọi
là Đảo ngược lỗi\footnote{Error reversal}.

\subsection{Các lỗi khác}

Ngoài hai loại lỗi trên, còn có nhiều nguyên nhân khác dẫn đến lỗi
chính tả. Một trong những nguyên nhân đó là lỗi dùng từ sai (do hiểu
sai, hoặc không hiểu rõ cách dùng từ). Đây thực chất thuộc về lỗi từ
vựng, nhưng đôi khi người dùng lại đòi hỏi trình bắt lỗi chính tả phải
tìm ra những lỗi này.

Ngoài lỗi dùng từ sai, còn có những lỗi phát sinh do máy móc. Hai công
cụ liên quan đến xử lý văn bản và dễ gây ra lỗi chính tả là nhận dạng
tiếng nói và nhận dạng chữ viết. Đối với nhận dạng tiếng nói, lỗi
thường gặp giống với dạng lỗi phát âm sai. Tuy nhiên, đối với một số
ngôn ngữ như tiếng Anh --- mỗi từ gồm nhiều âm tiết --- thì có thể gây
ra lỗi tách từ sai. Đối với nhận dạng văn bản, lỗi chủ yếu do sự giống
nhau giữa các chữ cái khi viết. Thông thường, bản thân các công cụ này
cũng được cài đặt một trình bắt lỗi chính tả tự động (dạng đơn giản
hoặc phức tạp) nhằm giảm thiểu các lỗi chính tả.

\section{Sắp xếp danh sách từ đề nghị}
\label{sec:sort-candidates}


Việc chọn từ tốt nhất trong danh sách từ đề nghị là một công việc không dễ
dàng. \cite{Agirre} mô tả cách lựa chọn trong trường hợp
này, có thể chia làm các nhóm như sau:

\begin{itemize}
\item Sử dụng phân tích cú pháp để loại bỏ những từ sai từ loại, hoặc
  sai các đặc trưng hình thái (số đếm, chữ hoa/chữ thường~\ldots{})
\item Khử nhập nhằng ngữ nghĩa để chọn từ phù hợp với ngữ cảnh nhất.
\item Dùng thống kê để chọn từ thường xuất hiện nhất.
\item Những từ có cách viết hoa/thường khác với từ bị sai sẽ bị loại
  (ví dụ, nếu từ viết sai là chữ thường thì các từ đề nghị viết hoa sẽ
  bị loại)
\end{itemize}


Một số kỹ thuật để sắp xếp danh sách từ được chọn sẽ được mô tả ngắn
gọn bên dưới.
%%% Giải thích cụ thể hơn.

\subsection{Văn phạm ràng buộc}

%-% Constraint Grammar a Language independent system for parsing
%-% unrestricted text.

Văn phạm ràng buộc\footnote{Constraint Grammar} (CG) được thiết kế
độc lập ngôn ngữ và là một công cụ mạnh giúp khử nhập nhằng các văn
bản không giới hạn~\cite{cg}. 

CG có thể được xem như một tập hợp các luật mẫu-hành
động\footnote{pattern-action rule}, không quá một luật với mỗi tag có nhập
nhằng. Mỗi luật xác định một hoặc nhiều mẫu (các ``ràng buộc'') xác
định khi nào tag đó không hợp lệ. Nếu thỏa một mẫu trong số các mẫu
của luật, tag đó sẽ bị xoá. Các mẫu ngữ cảnh có thể là mẫu cục bộ hoặc
toàn cục, có thể tham khảo những phân tích nhập nhằng hoặc không nhập
nhằng. Thuật toán sẽ được chạy vài lần để giảm nhập nhằng từ từ, nhờ đó
giúp các ngữ cảnh giảm nhập nhằng, hoặc không còn nhập nhằng, tạo điều
kiện khử nhập nhằng những từ khác.

Mô tả cú pháp và hình thái được mã hoá bằng tag thay vì cấu trúc đóng
mở ngoặc. Mô tả cú pháp rất nông. Mỗi từ được gắn với một tag chức
năng cú pháp\footnote{syntactic function tag}, quy định mô tả phụ
thuộc về mặc chức năng.

Các ràng buộc giúp tránh các dự đoán có nhiều rủi ro chứ không chọn ra
giải pháp đúng. Do đó CG chỉ giúp giảm số lượng các nhập nhằng. Văn
phạm ràng buộc tiếng Anh (EngCG) đã giúp cải thiện đáng kể chất 
lượng bộ đánh nhãn từ loại tiếng Anh. Văn phạm ràng buộc giúp loại bỏ
hầu hết các nhập nhằng có thể được.

XXX % vd


Việc áp dụng CG để khử nhập nhằng cho trình bắt lỗi chính tả là một
công việc khó khăn vì hiện nay CG cho tiếng Việt vẫn chưa được xây
dựng. 

\subsection{Mật độ quan niệm}
%-% Word Sense disambiguation using conceptual density 96.


Đây thực chất là áp dụng khử nhập nhằng ngữ nghĩa dùng
WordNet và độ đo khoảng cách giữa các khái niệm trong WordNet. Cách
này được áp dụng cho danh từ. 

WordNet là một mạng ngữ nghĩa về từ vựng tiếng Anh, bao gồm các mối
liên hệ khác nhau giữa các từ tiếng Anh. WordNet định nghĩa các quan
hệ khác nhau cho mỗi từ loại. Đối với danh từ thì hai loại quan hệ
quan trọng nhất là hypernym và hyponym. 

A được xem là hyponym của B
(và B là hypernym của A) nếu ta có thể nói ``A là một loại đặc biệt
của B''. Ví dụ, cây là một loại thực vật. Vậy cây là hyponym của thực
vật (và thực vật là hypernym của cây)

WordNet được tổ chức theo đơn vị là các synset. Synset
(Synonym set) là một nhóm các từ đồng nghĩa có thể dùng thay thế cho
nhau. Mỗi từ có thể thuộc nhiều synset khác nhau. Trong trường hợp đó,
các syset được gọi là sense của từ đó. Phần danh từ trong WordNet có
thể xem như một đồ thị của các synset và các liên kết hypernym/hyponym
giữa các synset đó.  

Độ đo khái niệm\footnote{conceptual distance} cung cấp một nền tảng để
đo độ giống nhau về mặt nghĩa của các từ. Độ đo khái niệm được định
nghĩa bởi \cite{Rada} là độ dài đường đi ngắn nhất liên kết các khái
niệm trong mạng ngữ nghĩa phân cấp.

Cho một khái niệm $c$ nằm trên đỉnh cây con và $nhyp$ là số hypernym
mỗi nút. Mật độ quan niệm\footnote{conceptual density} (CD) để khử nhập nhằng cho $c$ khi cây con của
nó chứa $m$ sense của từ đó  như sau:

$$CD(c,m)=\frac{\displaystyle\sum^{m-1}_{i=0}nhyp^{i^{0.20}}}{descendants_c}$$

Trong công thức trên, tham số $0,20$ được dùng để làm trơn hệ số mũ
$i$ khi $m$ chạy từ 1 đến số sense tổng cộng trong WordNet. Nhiều giá
trị đã được thử cho tham số này và tham số gần $0,20$ là tốt nhất.


Thuật toán khử nhập nhằng dựa trên CD như sau: Cho cửa sổ với kích
thước nhất định, chương trình di chuyển cửa sổ mỗi 
danh từ một lần, từ đầu câu cho đến hết, khử nhập nhằng cho danh từ ở
chính giữa cửa sổ, xem các danh từ còn lại trong cửa sổ là ngữ
cảnh. Đặt cửa sổ các danh từ là $W$ và danh từ chính giữa cửa sổ là
$w$, ta có:

\begin{algo}[Khử nhập nhằng danh từ dùng CD]
  \begin{enumerate}
  \item tree := compute\_tree(words\_in\_window).

    Loop
  \item tree := compute\_conceptual\_distance(tree)
  \item concept := select\_concept\_width\_highest\_weight(tree)
    
    if concept = null then exitloop
  \item tree := mark\_disambiguated\_senses(tree,concept)

    endloop
  \item output\_disambiguation\_result(tree)
  \end{enumerate}
\end{algo}

Đầu tiên, thuật toán thể hiện một dàn các danh từ trong cửa sổ, các
sense và hypernym của chúng (bước 1). Sau đó thuật toán tính
CD cho mỗi khái niệm trong WordNet tương ứng với sense
nó chứa trong cây con của nó (bước 2). Thuật toán chọn khái niệm $c$
với CD cao nhất (bước 3) và chọn sense đúng bên dưới
cho  những từ tương ứng (bước 4).

Thuật toán tiến hành tính CD cho những sense còn lại trong dàn, tiếp
tục khử nhập nhằng những danh từ còn lại trong cửa sổ (quay lại bước
2, 3, 4). Khi không thể khử nhập nhằng được nữa, những sense còn lại
của $w$ được xử lý và xuất kết quả ra (bước 5).

Giải pháp CD có hạn chế là chỉ áp dụng đối với danh từ. Những loại từ
khác, do có các mối quan hệ phức tạp hơn nhiều so với quan hệ hypernym
của danh từ nên rất khó áp dụng. CD đôi khi không thể khử nhập nhằng
tuyệt đối (chỉ chừa lại một kết quả) mà nhiều khi vẫn còn lại vài nhập
nhằng. Tuy nhiên việc giảm nhập nhằng bằng CD cũng giúp ít rất nhiều
cho trình bắt lỗi chính tả. 

Hạn chế quan trọng của CD khi áp dụng cho
tiếng Việt là thiếu WordNet dành cho tiếng Việt. Việc xây dựng một
mạng ngữ nghĩa tiếng Việt có tầm vóc như WordNet sẽ tốn rất nhiều công
sức, chưa kể các điểm khác biệt giữa tiếng Anh và tiếng Việt đòi hỏi
các nhà ngôn ngữ học phải xem xét lại có thể áp dụng hoàn toàn các mối quan hệ
đã được sử dụng trong WordNet hay không, hay cần phải loại bỏ và thêm
vào một số quan hệ khác cho phù hợp với tiếng Việt. Nói tóm lại, đây
là một giải pháp hay tuy nhiên không thể áp dụng trong điều kiện hiện
tại. Gần đây có nhiều đề tài nghiên cứu xây dựng WordNet tiếng
Việt. Hy vọng có thể áp dụng CD và các giải pháp dựa trên WordNet khác
cho tiếng Việt trong tương lai không xa.


\section{Tự động phát hiện và sửa lỗi chính tả}
\label{sec:context-spelling}

Tự động phát hiện và sửa lỗi chính tả được đặt ra để cải tiến các
chương trình bắt lỗi chính tả. Các chương trình bắt lỗi chính tả
truyền thống thường dựa trên từ điển, nên không thể bắt lỗi những từ
sai, nhưng lại có trong từ điển. Ví dụ, ``give me a peace of cake''
(lẽ ra phải là ``give me a piece of cake'') hoặc ``anh ấy là một người
bàng quang'' (trong khi phải là ``anh ấy là một người bàng
quan''). Hướng giải quyết là dựa vào tập nhầm lẫn để tìm ra những từ
có khả năng viết sai (ví dụ, ``peace-piece'' và ``bàng quang-bàng
quan'') sau đó dựa vào ngữ cảnh để xác định xem đang xét có phù hợp
với ngữ cảnh hay không. Bởi vậy bài toán này còn được gọi là bắt lỗi
chính tả cảm ngữ cảnh\footnote{context-sensitive spelling
  checking}. 
%% Đa số các thuật toán thường chuyển câu đang xét thành một
%% tập các đặc trưng rồi dựa vào đó để xem xét, hoặc sử dụng các mô hình
%% ngôn ngữ để đánh giá.

\subsection{Mô hình TBL}
\label{sec:tbl-spell}


TBL\footnote{Transformation-based Learning} là mô hình học có giám sát,
được Eric Brill đưa ra vào năm 1993. Đây là mô hình học luật dựa trên
lỗi, tạo ra các luật mới để khắc phục các lỗi còn lại sau khi đã áp
dụng các luật trước đó. TBL được áp dụng để tự động phát hiện và sửa
lỗi chính tả. TBL chỉ nhắm vào một tập lỗi thông dụng cho trước, chủ
yếu là loại lỗi dùng từ sai, loại lỗi rất khó bị phát hiện bởi các
trình bắt lỗi chính tả thông thường. Những lỗi không phải từ (lỗi nhập
liệu~\ldots{}) không được xử lý bởi TBL. Phương pháp này được áp dụng
bởi Lidia Mangu và Eric Brill~\cite{tbl} cho kết quả rất cao
(93,15\%).

TBL hoạt động như một bộ luật sửa lỗi. Dữ liệu ban đầu cần được một
chương trình khác (baseline) xử lý để phát hiện hiện và sửa lỗi chính tả. Mục
tiêu của chương trình này phát hiện và sửa đúng lỗi chính tả càng
nhiều càng tốt. Các lỗi gây ra bởi chương trình ban đầu này sẽ được
sửa bởi TBL. Các luật học được từ quá trình huấn luyện TBL sẽ được áp
dụng lần lượt theo thứ tự, sửa chữa các lỗi của do chương trình
baseline gây ra cũng như các lỗi do chính việc áp dụng luật TBL gây
ra. Kết quả là số lỗi sai chính tả sẽ giảm đáng kể.

Các luật trong TBL là các luật dạng mẫu-hành
động\footnote{pattern-action rule} sử dụng nhiều loại thông tin khác
nhau để xác định ngữ cảnh. Hành động trong luật thường là thay thế
từ đang xét bằng một từ khác. Các thông được sử dụng trong mẫu bao gồm
vị trí tương đối của các từ so với từ đang xét, từ loại, từ~\ldots{} Ba
loại mẫu được dùng trong~\cite{tbl} là:
\begin{itemize}
\item Từ $W$ xuất hiện trong phạm vi $\pm k$ từ chung quanh từ $w$
  đang xét.
\item Một mẫu xác định gồm $l$ từ/từ loại liên tiếp nhau xuất hiện
  chung quanh $w$.
\item Một mẫu xác định gồm các từ/từ loại không liên tiếp, xuất hiện
  quanh $w$.
\end{itemize}

Huấn luyện TBL giống như cách áp dụng luật TBL. Dữ liệu đầu vào là một
ngữ liệu đã được đánh dấu (từ đúng/từ sai --- nếu từ sai thì đi kèm
với từ đúng). Thực hiện các bước sau:
\begin{enumerate}
\item Gỡ bỏ các đánh dấu trong ngữ liệu, đưa trở về dạng ngữ liệu thô.
\item Đánh baseline cho ngữ liệu thô.
\item Dựa vào các mẫu luật, phát sinh các luật. 
\item Lần lượt áp dụng các luật lên ngữ liệu. 
\item Tính điểm cho ngữ liệu dựa trên ngữ liệu đã đánh dấu ban đầu,
  sau khi áp dụng từng luật lên ngữ   liệu. Điểm tăng nghĩa là kết quả
  đúng nhiều hơn so với khi chưa áp   dụng luật. Điểm âm nghĩa là kết
  quả sai nhiều hơn. 
\item Nếu điểm âm, bỏ qua luật này.
\item Nếu điểm dương, đưa luật vào danh sách luật.
\item Nếu điểm tăng ít hơn một giới hạn cho trước, dừng thuật toán.
\item Quay lại bước 4.
\end{enumerate}

Sau khi chấm dứt thuật toán, ta chọn khoảng $n$ luật đầu tiên. Những
luật còn lại bị loại bỏ. $n$ luật này chính là những luật kết quả của
quá trình huấn luyện theo mô hình TBL.

Việc áp dụng TBL đòi hỏi phải có ngữ liệu đã đánh dấu (ngữ liệu vàng),
một hàm tính điểm (được dùng trong bước 5), trình đánh dấu baseline,
và các mẫu luật. Ngoài ra còn có một số tham số (ngưỡng dừng thuật
toán, các tham số $n$, $k$, $l$~\ldots{} đã nêu trên). Việc chọn mẫu
luật và các tham số thích hợp ảnh hưởng nhiều đến hiệu quả của TBL.

Ngữ liệu đánh dấu có thể được tạo ra từ tập nhầm
lẫn\footnote{confusion set}. Tập nhầm lẫn xác định những từ thường bị
nhầm lẫn (Ví dụ, ``their'' và ``there'' hay ``đã'' và ``đả''~\ldots{})
Từ văn bản đúng chính tả, ta có thể áp dụng tập nhầm lẫn để tạo ra ngữ
liệu sai chính tả. Để thực hiện đều này cần có tập nhầm lẫn.

Nếu tập nhầm lẫn không chỉ bao gỗm các nhập nhằng về tiếng (hoặc từ
đơn) mà cả nhập nhằng về từ (Ví dụ ``bàn quan'' và ``bàng quang'') thì
cần phải có thêm một bộ tách từ.

Hiệu quả của TBL phụ thuộc vào tập nhầm lẫn. Tập nhầm lẫn càng lớn
thì khả năng sửa lỗi chính tả bằng TBL càng cao. Tuy nhiên, tập nhầm
lẫn càng lớn thì khả năng sai sót cũng càng lớn, và chương trình không
thể tập trung vào các lỗi thường gặp. Để TBL hiệu quả hơn, cần sử dụng
thông tin từ loại (hoặc phân lớp từ). Tuy nhiên, một khi chưa sửa lỗi
chính tả/tách từ xong thì việc tìm từ loại bằng các phương pháp thông
dụng trở nên không an toàn.


%\subsection{Mô hình n-gram}
%%% Mays et al 91 -> trigram


\subsection{Mô hình Winnow}

Bài toán bắt lỗi chính tả được xem như là bài toán khử nhập nhằng
từ. Các từ nhập nhằng được tập hợp thành tập nhầm lẫn. Tập nhầm lẫn $C
= \{W_1,\ldots{},W_n\}$ nghĩa là mỗi từ $W_i$ trong tập $C$ có thể bị
dùng lẫn lộn với các từ còn lại trong $C$.
Bài toán bao gồm một câu, và một từ cần sửa chữa. Thuật toán thể hiện
bài toán như là một danh sách các đặc trưng tích cực\footnote{active
  feature}. Mỗi đặc trưng tích cực thể hiện cho một ngữ cảnh cụ
thể. Hai loại đặc trưng được dùng là từ ngữ cảnh\footnote{context
  word} và collocation. Từ ngữ cảnh là một tập các từ nằm xung quanh
từ đang xét (giới hạn trong khoảng $\pm k$ từ tính từ từ đang
xét). Collocation là một mẫu $l$ từ/từ loại liên tiếp nhau xung quanh
từ đang xét.

Một bộ rút trích đặc trưng\footnote{feature extractor} được sử dụng để
chuyển văn bản gốc thành danh sách các đặc trưng tích cực. Bộ rút
trích đặc trưng phải được huấn luyện trước, để chỉ lọc ra những đặc
trưng nhất định (đặc trưng tích cực), thay vì tất cả các đặc trưng.

Để huấn luyện bộ rút trích đặc trưng, ta cho chạy bộ rút trích đặc
trưng trên ngữ liệu huấn luyện, rút trích tất cả các đặc trưng có thể
có, đồng thời thống kê số lượng của mỗi đặc trưng. Sau khi chạy xong,
danh sách đặc trưng này sẽ bị cắt bớt theo một tiêu chí cho trước, chỉ
chừa lại những đặc trưng được xem là tích cực. Có thể thu gọn danh
sách đặc trưng theo nhiều tiêu chí khác nhau. Tuy nhiên cách đơn giản
nhất là dựa vào tần số xuất hiện của các đặc trưng. Nếu các đặc trưng
xuất hiện ít hơn một ngưỡng nào đó thì đặc trưng đó bị loại bỏ.

Công việc mỗi bộ phân lớp là xác định từ $W_i$ trong tập nhầm lẫn có thuộc
về câu đang xét hay không. Mỗi bộ phân lớp chạy thuật toán Winnow. Bộ
phân lớp nhận tập các đặc trưng tích cực (đại diện cho câu đang xét),
trả về giá trị nhị phân cho biết từ $W_i$ có thuộc về câu đang xét hay
không. Đặt $F$ là tập các đặc trưng tích cực. Với mỗi $f\in F$, đặt
$w_f$ là trong số của cung nối $f$ với bộ phân lớp. Thuật toán Winnow
trả về giá trị 1 khi và chỉ khi $$\sum_{f\in F}w_f > \theta$$ trong đó
$\theta$ là tham số ngưỡng. 

Khởi đầu, bộ phân lớp không kết nối với bất kỳ đặc trưng nào trong
mạng. Trong quá trình huấn luyện, các kết nối và trọng số của kết nối
sẽ được thành lập. Một mẫu huấn luyện bao gồm một câu (tập đặc trưng
tích cực) cùng với từ $W_c$ trong tập nhầm lẫn. $W_c$ là từ đúng cho
câu trong mẫu huấn luyện đối với các mẫu khẳng định\footnote{positive
  example} và là từ sai trong các mẫu phủ định\footnote{negative
  example}. 

Quá trình huấn luyện được tiến hành theo như sau: lần lượt mỗi mẫu
được đưa vào hệ thống, các bộ phân lớp được cập nhật, sau đó mẫu bị
hủy.

Bước đầu tiên huấn luyện bộ phân lớp là thiết lập các liên kết
giữa bộ phân lớp và các đặc trưng tích cực $F$ trong mẫu. Nếu đặc
trựng tích cực $f \in F$ chưa được kết nối vào bộ phân lớp, và cầu là
mẫu khẳng định đối với bộ phân lớp, ta tạo một kết nối giữa đặc trưng
đó và bộ phân lớp với giá trị trọng số khởi đầu là $0,1$. Chú ý rằng
không có gì xảy ra với các mẫu phủ định. 

Bước kế tiếp là cập nhật trong số cho các liên kết. Bước này được thực
hiện nhờ vào luật cập nhật Winnow, chỉ cập nhật trọng số khi xảy ra
lỗi. Nếu bộ phân lớp dự đoán là 0 đối với một mẫu khẳng định (nghĩa là
lẽ ra bộ phân lớp phải dự đoán là 1), trong số sẽ được tăng:
$$\forall f \in F, w_f \leftarrow \alpha \cdot w_f$$
trong đó $\alpha > 1$ là tham số cho trước. Nếu bộ phân lớp dự đoán 1
với các mẫu phủ định (mà lẽ ra bộ phân lớp phải dự đoán là 0), trọng
số sẽ được giảm:
$$\forall f \in F, w_f \leftarrow \beta \cdot w_f$$
với $0 < \beta < 1$ là tham số cho trước. \cite{Golding99} đề nghị
$\alpha$ là $1,5$ và $\beta$ là $0,5$ đến $0,9$. Như vậy, trọng số của
các đặc trưng không tích cực sẽ giữ nguyên, không thay đổi. Thời gian
cập nhật của thuật toán phụ thuộc vào số đặc trưng tích cực trong mẫu.

Thay vì xử lý từ $W_i$ dựa trên một bộ phân lớp, ta có thể áp dụng kết
quả trả về của nhiều bộ phân lớp đồng thời. Mô hình Weighted Majority
được dùng để kết hợp nhiều bộ phân lớp. Ta cho chạy nhiều bộ phân lớp
đồng thời. Các bộ phân lớp trả về các giá trị khác nhau. Hiệu suất của
mỗi bộ phân lớp được theo dõi. Trọng số được tính toán để phản ánh độ
chính xác của bộ phân lớp. Giá trị sau cùng là tổng của các dự đoán
của các bộ phân lớp được xét, kèm với trọng số của mỗi bộ phân lớp.

Mô hình này được áp dụng trong~\cite{Golding99}.

\subsection{Mô hình Danh sách quyết định}
%%% Yarowsky 94 -> decision lists

Mô hình Danh sách quyết định được Yarowsky đưa ra để giải quyết bài
toán khử nhập nhằng ngữ nghĩa. Mô hình này dựa trên các đặc trưng quan
trọng để nhận dạng. Ngoài ra kết xuất của mô hình rất đơn giản, dễ
hiểu, tạo thuận lợi trong nghiên cứu, cải tiến mô hình. Phương pháp
này được~\cite{vietdecisionlist} áp dụng để bắt lỗi chính tả tiếng
Việt.

Mô hình có thể sử dụng nhiều loại đặc trưng khác nhau. Hai đặc trưng
thường được áp dụng là từ ngữ cảnh và collocation. 

Thuật toán của mô hình như sau:
\begin{enumerate}
\item Xét mỗi từ trong câu, có tập nhầm lẫn tương ứng là $S$.
\item Với mỗi từ $w \in S$:
  \begin{enumerate}
  \item Xác định tập đặc trưng $C_w$ không chứa các đặc trưng xung đột
    với các đặc trưng đã được chấp nhận trước đó.
  \item Tím điểm của từ:$$Score(w)=\underset{f\in C_w}{max}P(w|f)$$
    và xác định $$f_w = \underset{f\in C_w}{argmax}P(w|f)$$
  \end{enumerate}
\item Từ được chọn là $$a=\underset{w\in S}{argmax}Score(w)$$ Ghi nhớ
  thuộc tính $f_w$ để kiểm tra xung đột ở các vị trí khác.
\end{enumerate}

Quá trình huấn luyện mô hình như sau. 
\begin{itemize}
\item Bộ rút trích đặc trưng (tương tự
như trong mô hình Winnow) được sử dụng để rút ra các đặc trưng tích
cực từ các câu trong ngữ liệu huấn luyện.
\item  Đếm tần số xuất hiện của mỗi
đặc trưng. 
\item Loại bỏ các đặc trưng không đáng tin cậy (Ví dụ, tần số
quá thấp). 
\item Sắp xếp các đặc trưng theo thứ tự giảm dần khả năng quyết định.
\end{itemize}

\subsection{Mô hình Trigram và Bayes}

Mô hình sửa lỗi bằng Trigram rất đơn giản. Đối với mỗi câu, các từ
trong tập nhầm lẫn được thay thế cho từ tương ứng trong câu, sau đó
tính xác suất trigram của toàn bộ câu. Từ tương ứng với câu có xác
suất lớn nhất sẽ là từ được chọn. Cho câu $W =
w_1\ldots{} w_k\ldots{} w_n$, $w_k'$ là từ được dùng để thay thế cho
$w_k$, tạo ra câu mới $W'$. Nếu $P(W') > P(W)$ thì $w_k'$ sẽ được
chọn, với $P(W)$ và $P(W')$ lần lượt là xác suất trigram của câu $W$
và $W'$.

Một cải tiến của phương pháp này là
áp dụng trigram dựa trên từ loại thay vì trigram từ. Từ câu $W$, ta
tạo ra các chuỗi từ loại. Xác suất cuối cùng là:
\begin{align}
P(W)  &=\sum_T P(W,T)\\
P(W,T)&=P(W|T)P(T)\\
      &=\prod_i P(w_i|t_i)\prod_i P(t_i|t_{i-2}t_{i-1})
\end{align}
với $T$ là một chuỗi từ loại của $W$, $T=t_1\ldots{} t_n$ và
$P(t_i|t_{i-2}t_{i-1})$ là xác suất trigram từ loại.

Một mô hình khác để tìm và sửa lỗi chính tả là áp dụng bộ phân lớp
Bayes. Có thể xem đây là bài toán phân lớp từ dựa vào một tập các đặc
trưng. Từ cần xét là từ nằm trong tập nhầm lẫn, ta sẽ xét từ này và
các từ khác trong tập nhầm lẫn trong cùng ngữ cảnh. Tập đặc trưng
chính là ngữ cảnh của từ cần xét. Tập đặc trưng được rút trích từ câu
đang xét. Các đặc trưng và cách rút trích đặc trưng tương tự như trong
mô hình Winnow.

Mô hình Trigram và Bayes, mỗi cái có điểm mạnh riêng. Mô hình trigram
hoạt động tốt nếu những từ trong tập nhầm lẫn không cùng từ
loại. Ngược lại, khi không thể phân biệt dựa trên từ loại, mô hình
Bayes sẽ hoạt động tốt hơn do dựa vào các thông tin về cú pháp, ngữ
cảnh xung quanh. Do đó, giải pháp tốt nhất là kết hợp hai mô hình này
với nhau. Đầu tiên ta áp dụng mô hình Trigram. Trong quá trình xử lý,
nếu thấy mọi từ trong tập nhầm lẫn đều cùng từ loại, ta áp dụng mô
hình Bayes. Ngược lại, ta sẽ chấp nhận kết quả của mô hình
Trigram. Giải pháp này được áp dụng trong~\cite{Golding96}, tạo ra mô
hình Tribayes.


\subsection{Mô hình Bayes và Danh sách quyết định}
%%% Golding 95 -> hybrid method
Mô hình Danh sách quyết định là một mô hình mạnh. Tuy nhiên, có một
điểm cần lưu ý là mô hình này chỉ sử dụng {\em một} đặc trưng tốt nhất
để phân loại. Có lẽ tốt hơn là nên sử dụng {\em tất cả} các đặc trưng
để phân loại. Không có lý do gì để chỉ sử dụng một đặc trưng, trong
khi ta vẫn có thể khai thác các đặc trưng khác. Đây là nơi có thể cải
tiến bằng cách sử dụng bộ phân lớp Bayes.

Bộ phân lớp Bayes cũng sử
dụng một tập các đặc trưng, sắp theo thứ tự giảm dần hiệu quả. Bộ phân
lớp Bayes phân loại từ đang xét bằng cách sử dụng các đặc trưng. Tuy
nhiên, thay vì dừng lại sau khi áp dụng đặc trưng đầu tiên có thể sử
dụng, Bayes duyệt qua tất cả các đặc trưng, kết hợp tất cả các đặc
trưng, và giải quyết các xung đột giữa các đặc trưng nếu có, để đưa ra
kết quả sau cùng. Ta giả sử chỉ sử dụng các đặc trưng loại từ ngữ cảnh
và collocation. Nếu hai đặc trưng cần xét đều là từ ngữ cảnh,
 vậy sẽ không có xung đột. Nếu hai đặc trung đang xét đều
là collocation và chồng lên nhau, nghĩa là có xung đột. Đặc trưng xung
đột với đặc trưng đã xét trước đó sẽ bị bỏ qua, không được xem
xét.

Phương pháp này được đề nghị bởi~\cite{Golding95}.

\section{Bắt lỗi chính tả các ngôn ngữ châu Á}


Điểm đặc trưng dễ thấy giữa các ngôn ngữ châu Âu và các ngôn ngữ châu
Á, như tiếng Trung Quốc, tiếng Nhật, tiếng Hàn Quốc~\ldots{}, là ranh
giới từ. Đối với các thứ tiếng châu Âu, các cụm ký tự cách nhau bởi
khoảng trắng cũng là từ, do đó việc tách từ rất dễ dàng (chỉ phải
xử lý các trường hợp đặc biệt như dấu `-'~\ldots{}). Đối với các tiếng
châu Á, đặc biệt là tiếng Việt, công việc phức tạp hơn nhiều. Bởi vì
một ``từ'' như quan niệm châu Âu chỉ là một phần từ (một âm tiết trong
tiếng Việt) trong các ngôn ngữ châu Á. Điều này đặt ra một vấn đề mà
các chương trình bắt lỗi chính tả các thứ tiếng châu Âu chưa từng gặp
phải: phân ranh giới từ. 

Do các phương pháp dựa trên tiếng Anh đều ngầm định có thể tìm được
ranh giới từ ngay tức thì, nên khi áp dụng cho tiếng Trung Quốc,
tiếng Việt~\ldots{}{} không dễ dàng. Điểm khó khăn ở đây là nếu ta thay
một từ bằng một từ khác (trong tập nhầm lẫn) có độ dài không giống từ
trước đó, thì toàn bộ ranh giới từ phía sau sẽ bị thay đổi. Nói cách
khác, câu đã bị biến thành một câu khác (xét trên quan điểm câu là một
chuỗi các từ) khi thay đổi một từ trong câu.

Nếu không giải trực tiếp bài toán mà thực hiện tách từ trước, sau đó
mới bắt lỗi chính tả, thì khó khăn lại đè nặng lên phần tách từ.
Bài toán tìm ranh giới từ vốn đã phức tạp
(trong một số trường hợp, nếu không dựa vào thông tin ngữ nghĩa thì
không thể nào tách từ), lại càng phức tạp hơn khi áp dụng trong bài
toán bắt lỗi chính tả, vì khi đó ta phải tìm ranh giới từ khi {\em các
từ/tiếng đầu vào có thể không đúng}. Nói cách khác, ta phải thực hiện
tách từ trong điều kiện dữ liệu đầu vào không hoàn toàn chính xác:
tách từ mờ. Các kỹ thuật tách từ, nếu bỏ qua
yếu tố này sẽ dễ dẫn đến sai lầm, vì mọi phương pháp tách từ đều ngầm
định là dữ liệu đầu vào là chính xác. Sau khi tách từ xong, bài toán bắt
lỗi chính tả trở nên đơn giản. Ta có thể áp dụng các kỹ thuật đã được
áp dụng trên bắt lỗi chính tả các ngôn ngữ châu Âu dễ dàng.



%%% Bắt lỗi chính tả không tách từ, có không?

\section{Tách từ}

%\note{Liệt kê các phương pháp tách từ}
Bài toán tách từ cho ngôn ngữ đơn lập đã được đặt ra từ lâu, chủ yếu
để giải quyết cho tiếng Trung Quốc, tiếng Nhật. Các thuật toán tách từ có thể
được phân loại như sau:

\begin{description}
\item[Dựa theo luật] Bao gồm các cách sau:

  \begin{itemize}
  \item Longest Matching, Greedy Matching Models (Yuen Poowarawan, 1986;
    Sampan Rarurom, 1991)
  \item Mô hình khớp tối đa\footnote{Maximal Matching Model}. Mô hình
    này được chia thành ``khớp tối đa tiến''\footnote{forward maximum
    match} và ``khớp tối đa lùi''\footnote{backward maximum match}. Đối
    với phương pháp này thì một từ điển hoàn chỉnh là không thể
    thiếu. Một từ điển không hoàn chỉnh sẽ giảm hiệu suất của thuật
    toán. Tuy nhiên, dễ thấy là khó có thể có một từ điển hoàn chỉnh
    (đặc biệt khi các ngôn ngữ vẫn còn được tiếp tục phát triển hằng
    ngày trong thời đại ngày nay). Mô hình này tùy thuộc nhiều vào từ
    điển. 
%%     \begin{itemize}
%%     \item Thai, Sornlertlamvanich (1993).
%%     \item Chinese, Chih-Hao Tsai (1996), MMSeg 2000.
%%     \end{itemize}
  \end{itemize}
\item[Dùng thống kê]
  Giải pháp này dựa vào ngữ cảnh từ xung quanh để đưa ra quyết định
  thích hợp. Có hai vấn đề cần được giải quyết đối với giải pháp này:
  độ rộng ngữ cảnh, và cách áp dụng thống kê. Ngữ cảnh càng rộng thì
  thuật toán càng phức tạp.

  Cho dù độ rộng ngữ cảnh thế nào, luôn có thể áp dụng mô hình
  first-order HMM. Tuy nhiên giải pháp này phụ thuộc rất nhiều vào ngữ
  liệu huấn luyện. Kết quả huấn luyện trên ngữ liệu chính trị khó có
  thể áp dụng trên các tài liệu văn học và ngược lại. Thêm vào đó, có
  những từ có xác suất rất cao, nhưng chỉ có chứng năng về mặt ngữ
  pháp, làm giảm vai trò của xác suất.
%%   \begin{itemize}
%%   \item HMM dựa trên thuật toán Viterbi. (Asanee Kawtraku, 1995;
%%     Surapant,1995).
%%   \item EM. Xianping, 1996.
%%  \end{itemize}
\item[Các cách khác]
  Hầu hết các giải pháp khác là sự lai tạo giữa các mô hình trên và
  các mô hình ngôn ngữ học như WFST, TBL. Thời gian xử lý
  các giải pháp loại này trở nên đáng kể, nhưng độ chính xác đạt được
  khá cao.

  Tri thức về ngôn ngữ, thường được áp dụng cho các mô hình dựa trên
  luật, hiếm khi được áp dụng cho những mô hình trên.
\end{description}

Một số phương pháp tách từ được mô tả ngắn gọn bên dưới.

\subsection{Khớp tối đa}

Thuật toán so khớp tối đa hoạt động như tên của chính nó. Thuật toán
giải quyết bài toán tách từ bằng cách chọn cách tách từ nào có nhiều
từ nhất (so khớp được nhiều nhất). Thuật toán được áp dụng để xây dựng
chương trình tách từ tiếng Trung Quốc
MMSEG\footnote{http://casper.beckman.uiuc.edu/~c-tsai4/chinese/wordseg/mmseg.zip}.
Thuật toán này có nhiều biến thể khác nhau. 


\begin{itemize}
\item Dạng đơn giản, được dùng để giải quyết nhập nhằng từ đơn. Giả sử
  có một chuỗi ký tự (tương đương với chuỗi tiếng trong tiếng Việt)
  $C_1, C_2, \ldots{} C_n$. Ta bắt đầu từ đầu   chuỗi. Đầu tiên, kiểm
  tra xem $C_1$ có phải là từ hay không, sau đó kiểm tra xem $C_1C_2$
  có phải là từ hay không. Tiếp tục tìm cho đến khi tìm được từ dài
  nhất. Từ có vẻ hợp lý nhất sẽ là từ dài nhất. Chọn từ đó, sau đó tìm
  tiếp như trên trên những từ còn lại cho đến khi xác định được toàn
  bộ chuỗi từ.
\item Dạng phức tạp. Quy tắc của dạng này là phân đoạn có vẻ hợp lý
  nhất là đoạn ba từ với chiều dài tối đa. Thuật toán bắt đầu như dạng
  đơn giản. Nếu phát hiện ra những cách tách từ gây nhập nhằng (ví dụ,
  $C_1$ là từ và $C_1C_2$ cũng là từ), ta xem các chữ kế tiếp để tìm
  tất cả các đoạn ba từ có thể có bắt đầu với $C_1$ hoặc $C_1C_2$. Ví
  dụ ta được những đoạn sau: 
  \begin{itemize}
  \item $C_1\quad C_2\quad C_3C_4$
  \item $C_1C_2\quad C_3C_4\quad C_5$
  \item $C_1C_2\quad C_3C_4\quad C_5C_6$
  \end{itemize}
  Chuỗi dài nhất sẽ là chuỗi thứ ba. Vậy từ
  đầu tiên của chuỗi thứ ba ($C_1C_2$) sẽ được chọn. Thực hiện lại các
  bước cho đến khi được chuỗi từ hoàn chỉnh. Cách này đạt được độ
  chính xác 99.69\%~\cite{ChenLiu}.
\end{itemize}



\subsection{Mô hình HMM}

Trong cách áp dụng này, các trạng thái ẩn là các lớp từ, giả định rằng
mỗi từ có thể thuộc mọi lớp với một xác suất nhất định. Bài toán được
xem như tìm kiếm chuỗi lớp từ $C=c_1,\ldots{},c_n$ từ một chuỗi từ
$W=w_1,\ldots{},w_n$. Mục tiêu là tìm $W$ và $C$ từ câu $S$ cho trước,
sao cho tối đại xác suất$$\underset{W,C}{argmax}P(W|C)P(C)$$
Giả định rằng xác suất $P(W|C)$ chỉ phụ thuộc vào lớp từ của nó, và
xác suất lớp $P(C)$ chỉ phụ thuộc vào lớp của từ đứng trước. Những xác
suất này có thể được ước lượng bằng thuật toán Baum-Welch dùng ngữ
liệu huấn luyện. Tiến trình học dựa trên thuật toán Baum-Welch và
giống với bài toán đánh nhãn từ loại bằng HMM, trừ việc số trạng thái
được xác định trước và xác suất khởi đầu được gán ngẫu nhiên.

%% \subsection{Mô hình HHMM}

%% Mô hình Markov ẩn phân cấp (HHMM)\footnote{Hierarchical Hidden Markov
%%   Model}~\cite{hhmm} được áp dụng trong~\cite{hhmm2} để giải quyết bài toán tách từ
%% tiếng Trung Quốc.

%% Mô hình HMM\footnote{Hidden Markov Model} (L. R. Rabiner, 1989) là một
%% mô hình rất mạnh  để xử lý 
%% ngôn ngữ tự nhiên. Tuy nhiên, HMM truyền thống khó áp dụng hiệu quả
%% do một số hiện tượng phức tạp trong ngôn ngữ tự nhiên. Do vậy, Shai
%% Fine et al (1998) đã đưa ra mô hình HHMM, một mô hình đệ quy, tổng
%% quát hoá của HMM.

%% HHMM bao gồm sáu thành phần ($S$, $O$, $\Pi$, $A$, $B$, $D$). 
%% \begin{itemize}
%% \item $D$ là số mức sâu. 
%% \item $S$ là tập trạng thái hữu hạn. 
%% \item $O$ là bảng chữ cái kết quả hoặc kết xuất trung gian. 
%% \item $\Pi$ là xác suất trạng thái khởi đầu.
%% \item $A$ là xác suất chuyển trạng thái. 
%% \item $B$ là xác suất phát sinh các ký hiệu hoặc kết xuất trung gian. 
%% \end{itemize}
%% Sự khác nhau giữa HHMM và HMM là:
%% \begin{itemize}
%% \item Tập trạng thái $S$ có thể được tách làm nhiều tập con, tùy theo
%%   số mức của nó. Một trạng thái trong $S$ được đánh dấu bằng $q_i^d$
%%   với $(0<d\le D, 0<i\le|S^d|)$. Trong đó $d$ là chỉ số mức, $i$ là
%%   chỉ số trạng thái, $S^d$ là tập trạng thái mức $d$. Khi $d=D$,
%%   $q_i^d$ được gọi là trạng thái kết thúc vì its observation is
%%   symbols. Ngược lại, nó được gọi là trạng thái nội bộ vì observation
%%   của nó là từ HMM con của nó trong mức thứ $(d+1)$.
%% \item Mỗi trạng thái nội bộ $q^d$ $(0<d<D)$ có những trạng thái con
%%   của nó, hình thành một HMM độc lập. Trong HMM con, xác suất chuyển
%%   trạng thái là:
%%   $$A(q^d) = (a_{ij}(q^d)) = (P(q_j^{d+1}|q_i^{d+1}))$$
%%   Véc tơ phân bố khởi đầu là:
%%   $$\Pi(q^d)=(\pi^d(q_i^{d+1}))=(P(q_i^{d+1}|q^d))$$
%%   Trong đó $P(q_i^{d+1}|q^d)$ được định nghĩa là xác suất của trạng
%%   thái $q^d$ kích hoạt trạng thái con $q_i^{d+1}$ lúc ban đầu.
%% \item Chỉ có HMM dưới đáy có thể observe các ký hiệu. Xác suất phát
%%   ký hiệu tương ứng là:
%%   $$B(q^D)=(b_k(q^D))=(P(o_k|q^D))$$
%%   với $o_k$ nằm trong tập ký hiệu. Với mỗi HMM mức $d (d<D)$, chuỗi
%%   trạng thái trong các HMM con của nó có thể xem như là
%%   observation. Xác suất phát sinh có thể được ước lượng như trên.
%% \end{itemize}

%% HHMM bao gồm $D$ mức HMM mà mỗi mức này là một HMM độc lập. Hơn nữa,
%% mỗi HMM chỉ liên kết với cha và con của nó. Toàn bộ tập tham số của
%% HHMM được ký hiệu là:
%% \begin{align}
%% \lambda&=\{(\lambda(q^d))\}_{d\in\{1,\ldots{},D\}}\\
%%        &=\{\{A(q^d)\}_{d\in\{1,\ldots{},D-1\}},\{\Pi(q^d)\}_{d\in\{1,\ldots{},D-1\}},\{B(q^D)\}\}
%% \end{align}

%% HMM là dạng đặc biệt của HHMM, khi $D=1$.

%% Khi áp dụng HHMM để tách từ. Các từ chính là tập ký hiệu, còn các
%% tiếng chính là các trạng thái. Đến đây, ta quay về bài toán HMM truyền
%% thống. 

\subsection{Mô hình WFST và mạng nơ-ron}

WFST\footnote{Weighted Finite State Transducer} đã được~\cite{Sproat}
áp dụng để tách từ tiếng Trung Quốc. Ý tưởng cơ bản là áp dụng WFST
kết hợp với trọng số là xác suất xuất hiện của mỗi từ trong ngữ
liệu. Dùng WFST để duyệt qua câu cần xét. Cách duyệt có  trọng số lớn
nhất sẽ là cách tách từ được chọn. Giải pháp này cũng đã được áp dụng
trong Luận văn Tách từ tiếng Việt\footnote{Nguyễn Văn Toàn, Nguyễn Thi
  Minh Hằng -- Khoa Công nghệ thông tin, Khoá 97, Đại học Khoa học Tự
  nhiên} kèm với mạng nơ-ron để khử nhập nhằng. 

%% \subsection{Mô hình TBL}

%% TBL là mô hình học có thầy được Eric Brill đưa ra vào năm 1990. 

%% Việc áp dụng TBL đòi hỏi phải có một ngữ liệu tách từ sẵn. Tuy lượng
%% ngữ liệu không cần lớn như trong các cách áp dụng thống kê, nhưng vẫn
%% là một lượng đáng kể. Việc tạo một ngữ liệu như thế sẽ tốn rất nhiều
%% công sức. Đây là một điểm yếu (và cũng là điểm mạnh) của TBL.

\subsection{Mô hình Source-Channel cải tiến}
%-% cws-ACL03.pdf

Mô hình này được đề nghị trong~\cite{sc}.

Đặt $S$ là một câu tiếng Trung Quốc, hay là một chuỗi các ký tự (tương
đương chuỗi tiếng trong tiếng Việt). Với mỗi cách tách từ $W$ có thể
có, chọn cách tách từ tốt nhất $W^*$, tương ứng với xác suất điều kiện
$P(W|S)$:
$$W^*=\underset{w}{argmax}P(W|S)$$
Theo công thức Bayes, bỏ mẫu số là hằng số, ta được:
$$W^*=\underset{w}{argmax}P(W)P(S|W)$$
Ta định nghĩa lớp từ $C$ như sau:
\begin{itemize}
\item Mỗi từ được định nghĩa như một lớp.
\item Mỗi từ dẫn xuất hình thái được định nghĩa như một lớp.
\item Mỗi loại ký hiệu khác nhau được định nghĩa như một lớp. Ví dụ, các biểu
  thức thời gian thuộc về lớp TIME.
\item Mỗi loại tên riêng thuộc về một lớp. Ví dụ, tên người thuộc lớp PN.
\end{itemize}

Ta chuyển công thức trên qua các lớp từ:
$$C^*=\underset{c}{argmax}P(C)P(S|C)$$
Công thức trên là công thức cơ bản của mô hình source-channel cho tách
từ tiếng Trung Quốc. Mô hình giả định câu S được phát sinh như sau:
Đầu tiên, một người chọn một chuỗi khái niệm (ví dụ, lớp từ $C$) để
xuất ra, theo xác suất $P(C)$. Sau đó người đó cố gắng thể hiện các
khái niệm đó bằng chuỗi các ký tự, theo xác suất $P(S|C)$.

Mô hình source-channel có thể được hiểu theo một cách khác: $P(C)$ là
mô hình thống kê dự đoán xác suất của chuỗi lớp từ. Nó chỉ ra khả năng
một lớp từ xuất hiện, dựa trên một ngữ cảnh cho trước. Vậy $P(C)$ còn
được hiểu như {\em mô hình ngữ cảnh}. $P(S|C)$ là mô hình phát sinh,
dự đoán khả năng một chuỗi ký tự được phát sinh dựa trên lớp từ cho
trước. Vậy $P(S|C)$ còn được hiểu như {\em mô hình lớp}.

Mặc dù mô hình ngữ cảnh và mô hình lớp có thể được kết hợp bằng một
phép nhân đơn giản. Tuy nhiên nếu thêm trọng số thì kết quả tốt
hơn. Lý do là có một số mô hình lớp dự đoán kết quả rất không chính
xác. Hơn nữa, các mô hình lớp của các lớp từ khác nhau được xây dựng
theo những cách khác nhau. Vì vậy xác suất mô hình lớp khác nhau nhiều
giữa các mô hình lớp. Một cách để cân bằng những xác suất này là thêm
vào một trọng số $CW$ cho mỗi mô hình lớp để điều chỉnh xác suất
$P(S|C)$ thành $P(S|C)^{CW}$

Với mô hình đã có, thao tác tách từ bao gồm hai bước:
\begin{enumerate}
\item Cho chuỗi S, phát sinh mọi cách tách từ có thể có. Mỗi cách tách
  từ được đánh nhãn lớp từ và xác suất lớp $P(S'|C)$ với $S'$ là bất
  kỳ chuỗi con nào của $S$.
\item Thuật toán tìm kiếm Viterbi được áp dụng để chọn cách tách từ có
  khả năng nhất theo công thức nêu trên.
\end{enumerate}

\subsubsection{Huấn luyện}

Nếu có một dữ liệu được tách từ sẵn, công việc trở nên rất dễ
dàng. Tuy nhiên, việc xây dựng một ngữ liệu tách từ sẵn đủ lớn sẽ tốn
rất nhiều công sức (đặc biệt là các mô hình thống kê thường đòi hỏi
lượng ngữ liệu cực kỳ lớn, lớn hơn rất nhiều so với các mô hình dựa
trên luật). Để đơn giản vấn đề, ngữ liệu này được xây dựng tự động như
sau:
\begin{enumerate}
\item Khởi đầu, sử dụng một bộ tách từ sẵn có (có thể áp dụng các
  thuật giải đơn giản, không cần huấn luyện, như Longest matching,
  Maximum matching~\ldots{})
\item Sử dụng mô hình đề nghị để tách từ ngữ liệu huấn luyện.
\item Tái huấn luyện mô hình dựa trên kết quả tách từ có được ở bước
  2. Bước 2-3 có thể được lặp lại nhiều lần  cho đến khi hiệu suất của
  mô hình ngừng tăng.
\end{enumerate}

%%% give some comments about source-channel models.

%%% Giải thích rõ hơn về các mô hình

\subsection{Mô hình TBL}

Mô hình TBL (xem thêm phần~\ref{sec:tbl-spell}) cũng có thể được áp
dụng để tách từ tiếng Trung Quốc~\cite{palmer}. 

Mô hình TBL có thể được áp dụng cho nhiều bài toán khác nhau. Tùy vào
các hành động cụ thể của mẫu luật mà cách áp dụng sẽ khác nhau. Mẫu luật
áp dụng cho TBL sử dụng các hành động sau:    
\begin{itemize}
\item Nối hai ký tự (tiếng).
\item Tách hai ký tự.
\item Trượt ranh giới từ sang ký tự kế bên. 
\end{itemize}

Trình tách từ baseline, có thể áp dụng cách khớp tối đa.


%\subsection{Tách từ bằng bộ đánh nhãn}


\section{Tách từ mờ}

Như đã nói trên, bài toán tách từ không đơn thuần là tách từ đúng như
nghĩa ban đầu, mà là tách từ trong điều kiện dữ liệu đầu vào có khả
năng bị sai. Nói cách khác, đây là bài toán tách từ có khả năng chịu
lỗi\footnote{error-tolerant word segmentation}. Các phương pháp tách
từ được nêu, thông thường không thể áp dụng trực tiếp mà phải có một
số cải tiến nhất định nếu có thể. Ngoài ra cũng có thể áp dụng một số
giải pháp khác, tuy không trực tiếp áp dụng cho tách từ mờ, nhưng phần
nào có thể gợi ý cho một giải thuật tách từ mờ hiệu quả.

Kemal Oflazer~\cite{Oflazer} khi xử lý hình thái trong tiếng Thổ Nhĩ Kỳ gặp trường
hợp khá giống với trường hợp này. Tác giả phải tách hình thái từ
trong điều kiện từ đó bị sai chính tả. Do đặc tính
ngôn ngữ chắp dính\footnote{agglunative language}, số tiếp vĩ ngữ
nhiều, liên tiếp nhau, gây khó khăn cho việc nhận dạng tiếp vĩ ngữ,
cũng như không thể phân biệt những tiếng nào hợp thành một từ trong
một chuỗi tiếng trong tiếng Việt. Tác giả dùng một hàm độ đo, tạo ra
các tiếp đầu ngữ có khả năng thay thế dựa trên độ đo này, sau đó sử
dụng WFST để tìm chuỗi tiếp vĩ ngữ thích hợp nhất.

Bài toán nhận dạng tiếng nói trong tiếng Anh cũng gặp trường hợp tương
tự~\cite{Ravishankar}. Sau công đoạn xử lý âm thanh, ta nhận được 
một chuỗi các âm tiết. Ta phải chuyển nhóm âm tiết này thành
chuỗi từ. Do âm thanh thường bị nhiễu, nên các âm tiết có thể
không chính xác hoàn toàn. Ngoài ra, do đặc tính của tiếng Anh nên
cùng một chuỗi âm tiết có thể suy ra nhiều chuỗi từ khác nhau. Tác giả
sử dụng lưới từ để tạo ra các chuỗi từ có khả năng từ chuỗi âm tiết,
sau đó n-gram trên từ để lượng giá các chuỗi từ.

Một điểm đáng chú ý ở
đây là sự tương đồng về một mặt nào đó giữa tiếng Anh và tiếng
Việt. Với tiếng Anh, từ có thể tách dễ dàng, nhưng từ bao gồm nhiều âm
tiết. Việc phân ranh giới âm tiết trong tiếng Anh là một điều khá khó
khăn. Với tiếng Việt, các âm tiết được tách rất dễ dàng vì mỗi âm tiết
là một ``tiếng'' tương đương với một ``từ'' trong câu --- cách nhau
bởi khoảng trắng. Từ của tiếng Việt lại bao gồm nhiều tiếng, và việc
tách từ lại gặp nhiều khó khăn. Với nhận xét này, có thể thấy các bài
toán nhận dạng tiếng nói tiếng Anh gặp cùng vấn đề với bài toán bắt
lỗi chính tả tiếng Việt!

\cite{Chang} cũng dùng mô hình ngôn ngữ dạng n-gram để đánh giá các
cách tách từ sau khi đã qua tiền xử lý nhập nhằng chính tả, tuy nhiên
lại sử dùng nhiều mô hình ngôn ngữ khác nhau như 
character bigram, word bigram, inter-word character bigram (IWCB), POS
bigram, word class bigram. 

Dựa trên những nghiên cứu này, có thể thấy giải pháp khả thi cho việc
tách từ khi bị 
sai chính tả, là phát sinh một loạt các từ có khả năng thay thế, với
giả định trong tập từ này sẽ có từ đúng chính tả, thay thế từ sai chính
tả ban đầu. Sau đó sử dụng tách từ tìm một cách tách tốt nhất. Sau khi
tìm được cách tách từ, ta có thể tra từ điển để tìm xem từ nào bị sai.

\subsection{Huấn luyện}

Nếu có dữ liệu đã được đánh dấu sẵn các ranh giới từ, công việc đơn
giản chỉ là áp dụng các công thức thống kê để tính ra các giá trị cần
thiết.

Đối với việc huấn luyện các thuật toán tách từ truyền thống, ta có thể
sử dụng bộ tách từ tiếng Việt sẵn có để tạo ngữ liệu. Chất lượng của
bộ tách từ sẽ ảnh hưởng đến chất lượng của thuật toán.

Với các thuật toán tách từ mờ, đôi khi không thể áp dụng bộ tách từ
sẵn có. Với điều kiện hiện tại, khó có thể tìm được một khối lượng
ngữ liệu lớn đã được tách từ sẵn, do đó cần phải tìm giải pháp tính
được các tham số cần thiết từ ngữ liệu chưa được tách từ (ngữ liệu thô).

Thuật toán EM\footnote{Estimation Maximization} thường được áp dụng để vượt
qua khó khăn này~\cite{softcount,Sproat}. Trên lý thuyết, áp dụng
thuật toán EM đảm bảo kết quả sẽ hội tụ, và kết quả ở mỗi vòng lặp sau
sẽ tốt hơn hoặc bằng kết quả của vòng lặp trước. 
%Theo \cite{xxx}, ta chỉ cần lặp khoảng 5-7 vòng lặp là đủ.

Do thuật toán EM cũng có nhiều hạn chế (đặc biệt là hạn chế tối ưu cục
bộ), nhiều giải pháp đã được đưa ra để khắc phục các hạn chế
này~\cite{text-tiling,self-supervised}. 

Một giải pháp khác là áp dụng HMM để tìm ra ranh giới từ, sau đó áp
dụng các công thức thống kê thông thường. Giải pháp này gặp hạn chế
bởi chính HMM, vì HMM là mô hình thống kê thuần tuý, không phát huy
được một số đặc trưng của tách từ, cũng không sử dụng các tri thức về
ngôn ngữ học, do đó phần nào hạn chế kết quả cuối cùng. 

XXX

\chapter{Mô hình}
\label{cha:model}
\minitoc

% \note{Phân loại lỗi, nguyên nhân gây lỗi}

%%% cut it out, move it to somewhere
Ngoài ra, phải nói thêm là, do tiếng Việt là loại ngôn ngữ ``nói sao
viết vậy'', lại có sự phân hoá trong hệ thống âm vị của các miền, nên
khi viết thường rất dễ sai. Mức độ ``nhầm lẫn'' trong tiếng Việt cao
hơn hiều so với các thứ tiếng khác (như tiếng Anh). Với tiếng Anh,
thông thường mỗi tập nhầm lẫn chỉ gồm hai từ. Với tiếng Việt, đó có
thể là năm từ, thậm chí mười từ. Sự gia tăng kích thước của tập nhầm
lẫn làm hạn chế khả năng của các thuật toán bắt lỗi chính tả dựa trên
tập nhầm lẫn.


 \section{Lỗi chính tả}


\subsection{Phân loại lỗi}

Theo~\cite{LoiChinhTa}, lỗi bao gồm các loại sau:
\begin{itemize}
\item Lỗi thanh điệu. Chủ yếu là lỗi nhầm lẫn hai thanh hỏi, ngã.
\item Lỗi về âm đầu. Thường lẫn lộn các âm đầu sau: C/K, G/Gh, Ng/Ngh,
  Ch/Tr, S/X, V/D/Gi/R, W/Hw/Ngw/Qu.
\item Lỗi về âm chính. Thường lẫn lộn các âm chính sau: ai/ay/ây,
  ao/au/âu, ăm/âm, ăp/âp, iu/iêu/êu, im/iêm/em, ip/iêp/êp/ep,
  oi/ôi/ơi, om/ôm/ơm, op/ôp/ơp, ong/ông, oc/ôc, ui/uôi, um/uôm, up/(uôp),
  ưi/ươi, ưu/ươu, ưm/ươm, (ưp)/ươp.
\item Lỗi về âm cuối. Thường lẫn lộn chữ ghi các âm cuối trong các vần
  sau:
  an/ang, at/ac, ăn/ăng, ăt/ăc, ân/âng, ât/âc, en/eng, et/ec, ên/ênh,
  êt/êch, in/inh, it/ich, iên/iêng, iêt/iêc, ơn/(ơng), ơt/(ơc),
  un/ung, ut/uc, uôn/uông, uôt/uôc, ưn/ưng, ưt/ưc, ươn/ương, ươt/ươc.
\item Sai quy cách viết hoa
\end{itemize}

\noindent Theo \cite{Tuoi}, lỗi được phân làm hai loại:
\begin{itemize}
\item Từ bị sai không nằm trong từ điển. (do sai dấu hỏi---ngã, bỏ dấu
  không đúng vị trí, gõ nhầm ký tự trên bàn phím, gõ thiếu ký tự, gõ
  dư ký tự, gõ sai do gõ theo cách phát âm từng vùng, gõ nhầm vị trí
  các ký tự trong từ~\ldots{})
\item Từ bị sai nhưng vẫn có trong từ điển. (sai cách phát âm, nhầm ký
  tự, bỏ dấu sai, thiếu/thừa ký tự~\ldots{})
\end{itemize}

\noindent Theo \cite{Chang} thì lỗi bao gồm:
\begin{itemize}
\item Giống phiên âm
\item Giống hình dạng chữ viết
\item Giống nghĩa
\item Giống cách gõ
\end{itemize}

\section{Xử lý lỗi chính tả}
%%% Nêu tổng quan, nói cụ thể hơn ở phần sau ``previous work''

Với \cite{Tuoi} thì việc xử lý lỗi bao gồm:
\begin{itemize}
\item Từ không có trong từ điển thì bắt lỗi ở cấp từ vựng.
\item Từ có trong từ điển thị bắt lỗi ở cấp cú pháp.
\end{itemize}

%% Với \cite{Chang}, giải pháp gồm:
%% \begin{itemize}
%% \item Composite confusing character substitution
%% \item Advanced word class bigram language. LM score is composed base
%%   language model score and substitution penalty score.
%% \end{itemize}

%% qua các bước:
%% \begin{enumerate}
%% \item Input and Clause Segmentation
%% \item Composite Confusing Character Substitution
%% \item Language Model Evaluation
%% \item Comparision and Correction
%% \item Output
%% \end{enumerate}

Việc tìm lỗi dựa chủ yếu trên từ điển. So sánh từng từ trong câu với từ điển, những từ
không có trong từ điển là những từ có khả năng bị lỗi. Sau đó dựa trên
một số thuật giải hoặc các độ đo để tìm ra từ gần đúng với từ đó, chọn làm
từ đề nghị.

Việc tự động sửa lỗi chủ yếu dựa trên một tập các từ hay bị lỗi (then-than,
there-their~\ldots{}), sử dụng ngữ cảnh xung quanh để xác định từ đúng
hay sai.

Đối với ngôn ngữ đơn lập như tiếng Việt, vấn đề mới phát sinh là không
thể xác định rõ ràng ranh giới từ. Với tiếng Anh và các ngôn ngữ biến
cách khác, khoảng trắng thường được dùng để phân cách hai từ. Trong tiếng Việt,
khoảng trắng được dùng để phân cách hai tiếng. Ngoài ra, việc định
nghĩa từ trong tiếng Việt vẫn chưa thống nhất~\cite{worddef}. Luận văn
này sử dụng ``từ'' như là ``từ từ điển''.  

Để bắt lỗi chính tả trong tiếng Việt, có thể dựa trên nhiều cách khác
nhau. Cách đầu tiên đơn giản là tìm ranh giới từ cho tiếng Việt, sau
đó chuyển về bài toán bắt lỗi chính tả của tiếng Anh, dựa trên từ
điển. Cách khác là bắt lỗi mà không cần tách từ~\cite{Tuoi}
Cách nữa dựa trên ý tưởng ``phân tích cú pháp câu, nếu ta không thể
phân tích cú pháp của câu, nghĩa là câu đó sai chính tả''~\cite{iccc}.

Luận văn này làm theo hướng tách từ, sau đó tìm lỗi chính tả dựa trên
từ điển.



\subsection{Tách từ}

\cite{Sproat} sử dụng WFST để tách từ, huấn luyện bằng EM dựa trên
cách tách từ đúng nhất.

\cite{wordseg} sử dụng giải pháp tương tự như \cite{Sproat} nhưng cải
tiến bằng cách cáp dụng Neural Networks để giải quyết nhập nhằng dựa
vào POS. Nghiên cứu đề cập đến một số vấn đề tiền xử lý tiếng Việt như
xác định tên riêng, từ láy, phân tích hình thái.

\cite{Ravishankar} đề nghị tạo ra lưới từ\footnote{word lattice} sau
đó sử dụng thuật toán tìm đường đi ngắn nhất để tìm cách tách từ tốt
nhất dựa trên 2-gram hoặc 3-gram.

\cite{LAH} sử dụng n-gram và quy hoạch động để tách từ,
không dùng từ điển. Giải pháp này tương tự như \cite{softcount}, tuy
nhiên chỉ tính xác suất cách tách từ tốt nhất thay vì tính tổng xác
suất mọi cách tách từ như trong \cite{softcount}.

\cite{Chunyu} kết hợp ngram, lập trình quy hoạch động để tách từ. Xài
soft-count thay vì ``hard-count'' như \cite{Chang}. \cite{Chunyu} còn
đề nghị dùng case-based learning.

\subsection{Huấn luyện tách từ}

\note{Tại sao không xài bộ tách từ đã có?} Hai vấn đề:
\begin{itemize}
\item Chất lượng của bộ tách từ hiện có. (2-gram tốt hơn unigram~\ldots{}...)
\item Nếu thống kê trên mọi cách tách từ thì không thể dùng bộ tách từ
  hiện có vì chỉ tạo ra kết quả sau cùng.
\end{itemize}


Có thể huấn luyện dựa trên dữ liệu mẫu, hoặc dữ liệu thô. Do hầu hết
các phương pháp tách từ đều dựa trên ngram ($n\ge 1$) nên rất cần có
khối lượng dữ liệu huấn luyện lớn nhằm đạt tính bao quát. Dữ liệu
mẫu, được tách từ sẵn, thường không đủ để huấn luyện. Giải pháp chủ
yếu là huấn luyện dựa trên dữ liệu thô, chưa tách từ.

Thuật toán thường dùng nhất để huấn luyện trên dữ liệu thô là thuật
toán EM. Nhiều người đã cố gắng cải tiến EM theo nhiều cách khác nhau
nhằm nâng cao chất lượng huấn luyện, đồng thời hạn chế những khuyết
điểm của EM. 

\cite{self-supervised} đề nghị cách giải quyết hạn chế ``tối ưu cục
bộ'' của EM, bằng cách phân phối lại từ vựng sau mỗi lần chạy và khởi
động lại EM với điểm khởi đầu tốt hơn.

\cite{text-tiling} sử dụng một lượng nhỏ ngữ liệu huấn luyện có chất
lượng cao (\textit{seed set}) và một lượng lớn ngữ liệu có chất lượng
không thật bảo đảm (\textit{training set}), xử lý qua 4 bước:
\begin{enumerate}
\item \textbf{Phân đoạn tập huấn luyện}
\item \textbf{Phân hạng tập huấn luyện}
\item \textbf{Tổ hợp tập huấn luyện}
\item \textbf{Language model pruning}
\end{enumerate}



\section{Mô hình chung}

Việc bắt lỗi chính tả của một văn bản được xử lý lần lượt qua những
bước sau:
\begin{enumerate}
\item \textbf{Tiền xử lý} Tách văn bản thành những đoạn ngắn. Tách
  đoạn thành từng tiếng. Đánh dấu các ký hiệu, dấu ngắt dòng, các số,
  tên riêng~\ldots{}
\item \textbf{Bắt lỗi tiếng} Kiểm tra các tiếng với các tiếng đã có
  trong từ điển. Báo lỗi những tiếng không có trong từ điển. Sau đó 
  \textbf{Đưa ra giải pháp thay thế}.
\item \textbf{Tạo lưới từ} Tìm ra mọi từ có thể có trong câu. Xem
  giải thích về lưới từ bên dưới. Lồng trong phần này là phần
  \textbf{Phát sinh từ thay thế}
\item \textbf{Tách từ} Dựa vào lưới từ, đưa ra cách tách từ tốt nhất.
\item \textbf{Bắt lỗi từ} Dựa vào từ điển và cách tách từ đã có,
  tìm những từ nào không có trong từ điển. Những từ này được xem là từ
  sai. Sau đó \textbf{Đưa ra giải pháp thay thế}
\end{enumerate}

\section{Tiền xử lý}
\label{sub:preprocess}

Dựa vào flex để tách thành các token. Mục đích là để tách các dấu câu
ra khỏi tiếng. Ví dụ \fbox{"chào"} sẽ được tách thành 3 token
\fbox{"} \fbox{chào} \fbox{"}. Quy tắc được dùng như sau:

\begin{verbatim}

SENTENCE_FINAL                  [.?!]
HYPHEN                          [\-]
OPEN_SINGLE_QUOTE               [\`]
CLOSE_SINGLE_QUOTE              [\']
RIGHT_PAREN                     [\"\)\]\}\>\']


LETTERS_AND_NUMBERS             [a-zA-Z0-9]
LETTERS_NUMBER_AND_THEN_SOME    [a-zA-Z0-9]
APOSTROPHE                      \'

SINGLE_CHARACTER                [a-zA-Z0-9]

WHITE_SPACE                     [ \t\n]
NEWLINE                         [\n]
INVISIBLE                       [^\040-\176]


{SENTENCE_FINAL}+{RIGHT_PAREN}*                                 |
{HYPHEN}+                                                       |
{OPEN_SINGLE_QUOTE}+                                            |
{CLOSE_SINGLE_QUOTE}+                                           |

{LETTERS_NUMBER_AND_THEN_SOME}+{LETTERS_AND_NUMBERS}            |
{LETTERS_AND_NUMBERS}+{APOSTROPHE}                              |

{SINGLE_CHARACTER}                   { xuất từ }

({WHITE_SPACE}|{INVISIBLE}|{NEWLINE})+                { bỏ qua }

\end{verbatim}


\subsection{Tách câu}

Dựa vào các dấu câu để ngắt câu ra thành từng đoạn để xử lý. Mỗi
đoạn sẽ được xử lý độc lập với nhau. Đoạn ở đây có thể là một câu,
nhưng cũng có thể là một 
phần của câu. Luận văn này sẽ dùng từ ``câu'' để ám chỉ ``đoạn''. Nếu
các thông tin ở mức cao hơn được sử dụng (như thông tin cú pháp, ngữ
nghĩa~\ldots{}) thì phải thật sự xử lý trên câu chứ không phải trên 
đoạn. Các đoạn được phân cách bởi các dấu câu \fbox{.} \fbox{,}
\fbox{;} \fbox{(} \fbox{)}~\ldots{} 

\subsection{Chuẩn hoá}

Do trong tiếng Việt có nhiều từ có thể viết theo các
cách khác nhau về vị trí dấu thanh điệu, ví dụ, ``hoà'' và
``hòa''. Bởi vậy cần phải chuẩn hoá sao cho chương trình xem ``hòa''
và ``hoà'' là một. Giải pháp đưa ra là tách dấu thanh điệu ra khỏi
từ, biểu diễn dấu thanh điệu bằng ký tự đầu tiên trong từ. Như vậy,
``hoà'' và ``hòa'' đều có cùng cách biểu diễn là ``2hoa'', trong khi
đó ``hoa'' được biểu diễn là ``0hoa'', ``hồng'' được biểu diễn là
``2hông''.

\subsection{Chữ viết hoa}

Xử lý chữ viết hoa. Chữ viết hoa dùng để biểu diễn tên riêng, từ viết
tắt hoặc dùng cho chữ đứng đầu câu. Do đó cần phân biệt chữ đầu câu có
phải là chữ bắt đầu tên riêng hay không. Ngoài ra, cần xác định tên riêng khi
tìm được chữ viết hoa bắt đầu tên riêng. Các văn bản tiếng Việt chưa
hoàn toàn thống nhất về quy tắc viết hoa. Ví dụ, có tài liệu dùng
``Cộng hoà Xã hội Chủ nghĩa Việt Nam'', nhưng có tài liệu lại dùng
``Cộng Hoà Xã Hội Chủ Nghĩa Việt Nam''.

Do văn bản đầu vào có khả năng bị sai chính tả nên không thể xác định
ngay chính xác có phải là cụm từ viết hoa đúng hay không. Bước này cố
gắng phát hiện ra những cụm từ viết hoa và thêm vào lưới từ. Do vậy,
phần này được thực hiện bên trong phần \textbf{Phát sinh từ thay thế}. 

Có thể dùng thuật giải như sau: Nếu bắt đầu bằng chữ viết hoa, và chữ
đầu được viết thường cùng những từ kế tiếp của nó là một từ trong từ
điển, thì xem như đó là một từ. Nếu một chuỗi từ viết hoa liên tục
(hai từ trở lên) thì xem như đó là một từ (một tên riêng), và được
đánh dấu từ lạ $UNK$.

Với tên riêng của người Việt. Một danh sách các tên tiếng Việt được
thu thập nhằm rút ra những chữ thường dùng khi đặt tên. Những chuỗi
các chữ hoa liên tiếp được hình thành từ những chữ trong danh sách này
sẽ được xem như là tên riêng, đánh mã $PROP$.


%% \begin{algo}[Xử lý chữ hoa]
%% \label{algo:propername}
%%   \begin{enumerate}
%%   \item Lấy 1 chữ. Kiểm tra ký tự đầu tiên xem có phải ký tự hoa hay
%%     không.
%%   \item Nếu đây là chữ đầu câu, phát sinh bình thường dựa theo bản
%%     viết thường của chữ này. Ngoài ra tiếp tục thực hiện các bước
%%     dưới.
%%   \item Duyệt từ chữ đó trở đi, lấy chuỗi dài nhất có thể dựa trên
%%     $sid$. Phát sinh từ mới dựa trên từ lấy được. Đặt xác suất 0.80.
%%   \item Nếu không tìm được từ nào, duyệt lại như bước trên, dùng
%%     $scid$.
%%   \item Nếu chữ kế tiếp cũng là chữ hoa, duyệt từ đó trở đi để lấy
%%     chuỗi chữ hoa dài nhất ($scid$). Phát sinh từ mới
%%     mã $PROP$. 
%%   \end{enumerate}
%% \end{algo}

\subsection{Từ láy UNIMPL}

Phần này được thực hiện bên trong phần \textbf{Phát sinh từ thay thế}.

\begin{itemize}
\item Láy toàn bộ (Vd. ba ba, chuồn chuồn~\ldots{})
\item Láy âm đầu (Vd. chặt chẽ, trong trẻo~\ldots{})
\item Láy điệp vần (Vd. lông bông, lã chã~\ldots{})
\item Láy điệp âm, láy vần (Vd. thủ thỉ, tủm tỉm~\ldots{})
\item Hai thanh của tiếng thường ở cùng một hệ~\ldots{}
\end{itemize}

\note{Hổng thèm làm :-)} Vấn đề từ láy cũng tương tự như  tên riêng. Giải
pháp có thể áp dụng là dựa vào các quy tắc tạo từ láy để phát hiện
những từ có khả năng là từ láy và thêm vào lưới từ. 

Đối với các từ láy trên 2 tiếng. Do số lượng các từ láy dạng này không
nhiều nên có thể thêm các từ láy này vào từ điển.
%% Nhưng những ``từ láy''
%% ``nhưng những'' có thể giết chết module tách từ một cách êm dịu. Chắc
%% nên áp dụng giải pháp ``80 từ láy, 20 từ thường''. Không biết được hay
%% không, phiêu quá~\ldots{}

\begin{algo}[Xử lý từ láy]
\label{algo:poem}
  \begin{enumerate}
  \item Lấy 2 chữ liên tiếp.
  \item Kiểm tra quy tắt từ láy.
  \item Nếu đúng, phát sinh thêm từ láy mới, mã $POEM$.
  \end{enumerate}
\end{algo}

%% Có lẽ nên lọc ra danh sách từ láy bằng tay, đánh nhãn toàn bộ là
%% $POEM$, hoặc dùng nhãn riêng. Heuristic này không đáng tin lắm.
%% Cách hình thành từ láy của con người như thế nào ?? Từ láy thường gắn
%% liền với hình tượng, cảm giác gì đó. Làm sao người ta có thể cảm nhận
%% được một từ có phải là từ láy hay không??

\subsection{Từ nước ngoài, từ viết tắt, các ký hiệu~\ldots{}}

\note{Coi như từ sai chính tả}
\note{không phân biệt từ nước ngoài và từ sai chính tả}
Xử lý tiếng nước ngoài, các ký hiệu chuyên ngành, các từ viết tắt. Do
trình bắt lỗi không có kiến thức về các lĩnh vực chuyên 
ngành, cũng như các thứ tiếng trên thế giới, nên việc áp dụng tri thức
để phân loại là điều hết sức khó khăn. Giải pháp được dùng ở đây là
coi tất cả những từ nước ngoài, từ viết tắt, ký hiệu~\ldots{} đều là sai
chính tả, trừ khi được người dùng được vào danh sách từ nước ngoài, từ
viết tắt. Các con số được đánh dấu riêng bằng mã $NUM$.
``Số'' ở đây được coi là bất cứ chữ nào bắt đầu bằng số. Ví dụ, ``0lit'',
``0.2'', ``0-4''~\ldots{}{} đều được coi là số. 

\section{Phát sinh từ thay thế}

Phần này được sử dụng trong lúc tạo lưới từ và kiểm tra chính
tả. Mục đích là, cho trước một từ, phát sinh những từ ``gần giống''
với từ đó. Việc định nghĩa như thế nào là ``giống'' ở đây dựa theo các
nguyên nhân gây ra lỗi chính tả:
\begin{itemize}
\item Lỗi phát âm. Ví dụ, ``vu'' và ``du''. 
\item Do lỗi bàn phím. Có thể do gõ nhầm những phím lân cận. Ví dụ: gõ
  ``tôi'' thành ``tôu''. Khắc phục lỗi này dựa vào bố trí phím trên
  bàn phím. Độ đo là khoảng cách từ phím tạo ra ký tự trong từ cho
  trước và những từ chung quanh. Thông thường lỗi này chỉ xảy ra một
  lần trong mỗi từ. Ngoài ra còn lỗi liên quan đến cách kiểu gõ tiếng
  Việt.
\item Lỗi OCR\footnote{Optical Character Recognition}. Lỗi dạng này
  phụ thuộc nhiều vào phông chữ được dùng trên văn bản giấy. Tuy nhiên
  vẫn có một số lỗi chung như ``a'' và ``c'', ``d'' và ``cl''~\ldots{}
\item Lỗi sai về mặt từ vựng, cú pháp. Lỗi này hiện thời không xử lý
  do cần nhiều tri thức về ngôn ngữ tiếng Việt.
\item Lỗi không rõ nguyên nhân. Với dạng lỗi này, ta dùng hàm độ đo,
  tính số lần thêm/xóa/thay đổi/hoán vị mỗi ký tự giữa hai từ. Hàm độ đo
  được dùng được nêu trong \cite{Oflazer}, sẽ được trình bày lại bên
  dưới.
\end{itemize}

%% \note{Hmm..} có lẽ nên gắng thêm vào các từ phát sinh một ``hệ số chính
%% xác''. Từ gốc là từ có hệ số chính xác cao hơn so với các từ được phát
%% sinh. Good or bad? Hmmm... Làm sao để làm? Hmmm Hmmm

\subsection{Lỗi phát âm}

Lỗi phát âm phụ thuộc vào cách phát âm của từng
vùng. \cite{LoiChinhTa} liệt kê các trường hợp lỗi thông dụng
nhất. Những quy tắc này được áp dụng để, ví dụ, từ   ``du'' ta tạo ra
``vu''. 

Để phát sinh từ dựa trên lỗi phát âm, cần phân tích cấu trúc của từng
tiếng. Một tiếng bao gồm âm đầu, vần và thanh. Vần gồm âm đệm, âm
chính và âm cuối. Trong các thành phần của tiếng, âm chính là bắt buộc
phải có. Các thành phần còn lại có thể không có. Ta có thể biểu diễn
cấu trúc âm tiếng theo sơ đồ trạng thái như hình~\ref{fig:syllable}.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\textwidth]{syllable}
  \caption{Sơ đồ trạng thái phân tích cấu trúc tiếng}
  \label{fig:syllable}
\end{figure}

Khi phân tích tiếng, có thể có một số nhập nhằng giữa các thành phần
của tiếng. Vd, ``lúa'' bao gồm âm chính ``ua'' hay âm đệm ``u'' và âm
chính ``a''~\ldots{}

Ta có thể phân tích tiếng dùng FST. Tuy nhiên, qua
 hình~\ref{fig:syllable}
 có thể thấy chỉ có tám cách để hình thành
tiếng. Cài đặt theo tám cách này đơn giản và hiệu quả hơn dùng FST
tổng quát. Việc sắp xếp thứ tự áp dụng từng cách và một số heuristic
sẽ giúp loại bỏ nhập nhằng khi phân tích tiếng. 

\subsection{Lỗi bàn phím UNIMPL}

Chương trình giả định sơ đồ bố trí của bàn phím EN-US được dùng. Do
thông thường chỉ gặp một lỗi gõ nhầm với phím ngay bên cạnh này mỗi
từ, nên chương trình chỉ lưu danh  sách những phím lân cận với từng
phím, dựa trên bàn phím EN-US. Ví dụ: $A \rightarrow (S,Q,W,X,Z)$. 

Với những phím có hai ký tự như phím `2' (2 và @) thì @ sẽ được thêm
vào tập các phím lân cận với 2 và ngược lại.

Do với mỗi phím có khoảng 8 phím lân cận. Một chữ dài trung bình 8 ký
tự sẽ phát sinh ra một tập $8^8$ các chuỗi có khả năng. Trong số này
chỉ có một số rất ít là chữ thật sự, đúng quy tắc chính tả. Tuy nhiên
việc xử lý một khối lượng lớn như vậy là không thể. Vì vậy chương
trình giả định chỉ nhập gõ sai tối đa hai phím với mỗi chữ, nhằm giảm
thiểu bùng nổ tổ hợp.

Với các kiểu gõ như VNI, TELEX. Chương trình cố gắng ``phục hồi'' từ
những chữ gõ sai nếu phát hiện được. Vd, ``nguyê4n'' sẽ tạo ra
``nguyễn''. Ta cài đặt bộ gõ VNI, TELEX, sau đó đưa chuỗi các ký tự
của chữ đang xét qua bộ gõ phục hồi các dấu. Bước này được thực hiện
sau bước trên, để nếu gõ nhầm phím dấu kế bên thì vẫn có thể phục hồi
lại.

% Hmm.. phần phục hồi ngược từ VNI, TELEX. Vd, englíh (english). Cái này
% nhường cho English Speller. Hơi vướng với VIQR.

\subsection{Lỗi không rõ nguyên nhân UNIMPL}

\label{algo:ed}
Lỗi này dựa vào {\em độ đo khoảng cách hiệu chỉnh} được đề cập
trong \cite{Oflazer}. Các thao tác hiệu chỉnh được đo gồm {\em chèn,
xóa, thay thế một ký tự} hoặc {\em hoán vị hai ký tự kề nhau}, để có
thể chuyển đổi từ này thành từ kia. Đặt $X = x_1, x_2, \ldots{}, x_m$ và
$Y = y_1,y_2,\ldots{},y_n$ là hai chuỗi có độ dài tương ứng là $m$ và
$n$. $X[i]\quad(Y[j])$ biểu diễn chuỗi con ban đầu của X (Y) từ đầu từ
đến ký tự thứ $j$. Cho $X$ và $Y$, độ đo $ed(X[m],Y[n])$ được tính như
sau:
\begin{equation}
\begin{array}{rll}
  ed(X[i+1],Y[j+1]) &= ed(X[i],Y[j]) & \text{nếu $x_{i+1}=y_{j+1}$
  (ký tự cuối như nhau)}\\
                    &= 1+min\{ed(X[i-1],Y[j-1]), & \text{nếu $x_i=y_{j+1}$}\\
                    &\qquad\qquad ed(X[i+1],Y[j]), & \text{và $x_{i+1}=y_j$}\\
                    &\qquad\qquad ed(X[i],Y[j+1])\}\\
                    &= 1+min\{ed(X[i],Y[j]),&\text{trường hợp khác}\\
                    &\qquad\qquad ed(X[i+1],Y[j]),\\
                    &\qquad\qquad ed(X[i],Y[j+1])\}\\
  ed(X[0],Y[j])     &=j & 0 \le j \le n\\
  ed(X[i],Y[j])     &=i & 0 \le i \le n\\\\
  ed(X[-1],Y[j])    &=ed(X[i],Y[-1]) = max(m,n)&\text{Biên}
\end{array}
\end{equation}

Thuật toán có thể được khử đệ quy khi cài đặt bằng quy hoạch
động. Nhận thấy $ed(X[i+1],Y[i+1])$ cần dùng
$ed(X[i],Y[i])$,$ed(X[i-1],Y[i-1])$,$ed(X[i],Y[i+1])$ hoặc
$ed(X[i+1],Y[i])$, ta có thể tính từ lần lượt từ thấp đến cao theo
đường zig-zag bắt đầu từ đỉnh (1,1), sau đó đến đường chéo phụ (1,2),
(2,1), rồi đường chéo (1,3),(2,2),(3,1)~\ldots{}

\begin{algo}[Tính hàm ed()]
  \begin{enumerate}
  \item Đặt (0,0) là 0 nếu x[0] = y[0] hoặc 1 nếu ngược lại.
  \item Đặt (0,j) là j
  \item Đặt (i,0) là i
  \item (i,j)=(i-1,j-1) nếu x[i]=y[j]
  \item (i,j)=1+min\{(i-2,j-2),(i,j-1),(i-1,j)\} nếu x[i] = y[j-1]
    hoặc x[i-1]=y[j]
  \item (i,j)=1+min\{(i-1,j-1),(i,j-1),(i-1,j)\} trong các trường hợp còn lại
  \end{enumerate}
\end{algo}

Ví dụ: tính độ sai khác giữa chữ ``thắng'' và ``tắgn''. Ta tính các
giá trị như bảng~\ref{tab:ed-example}. Vậy có hai khác biệt giữa hai
chữ. Khác biệt thứ nhất là xoá ký tự `h'. Khác biệt thứ hai là hoán vị
hay ký tự `n' và `g'.

\begin{table}[htbp]
  \centering
  \begin{tabular}{|c|c|c|c|c|c|c|}
    \hline
    X&-&-&t&ắ&g&n\\\hline
    -&0&0&0&0&0&0\\\hline
    -&0&0&1&2&3&4\\\hline
    t&0&1&\bf 0&\bf 1&\bf 2&\bf 3\\\hline
    h&0&2&\bf 1&\bf 1&\bf 2&\bf 3\\\hline
    ắ&0&3&\bf 2&\bf 1&\bf 1&\bf 2\\\hline
    n&0&4&\bf 3&\bf 2&\bf 2&\bf 1\\\hline
    g&0&5&\bf 4&\bf 3&\bf 2&\bf 2\\\hline
  \end{tabular}
  \caption{Bảng $ed$ của ``thắng'' và ``tắgn''}
  \label{tab:ed-example}
\end{table}

\section{Tạo lưới từ}
\label{sub:lattice}
Lưới từ\footnote{word lattice} là một đồ thị có hướng không chu trình,
với các nút là các từ trong câu, cạnh là đường nối giữa hai từ kề
nhau, hướng thể hiện hướng của câu (từ trái sang phải). Lưới từ
chứa tất cả 
các từ có khả năng xuất hiện trong câu. Các từ được liên kết với nhau
theo trật tự trong câu. Khi duyệt từ nút gốc đến nút đích, ta sẽ được
một cách tách từ cho câu. Xem hình~\ref{fig:wordlattice}.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\textwidth]{wordlattice}
  \caption{Lưới từ của câu ``Học sinh học sinh học''}
  \label{fig:wordlattice}
\end{figure}

Khi tạo lưới từ trong chương trình bắt lỗi chính tả, thuật toán không
chỉ phát sinh những từ được tạo từ đoạn, mà còn những từ {\em có thể
có} được phát sinh từ đoạn. Xem hình~\ref{fig:wordlattice1}.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\textwidth]{wordlattice1}
  \caption{Lưới từ mở rộng của câu ``Học sinh học sinh học''}
  \label{fig:wordlattice1}
\end{figure}

Lưới từ được tạo bằng thuật toán Viterbi. Mỗi tiếng trong câu được
duyệt qua để tìm ra tất cả các từ có thể có trong đoạn. Sau đó tập hợp
các từ này lại. 

\begin{algo}[Tạo lưới từ (cơ bản)]
Cho câu S có n tiếng. State là đỉnh, còn ``nút i'' là cạnh. Ta duyệt
lần lượt qua các cạnh để tìm  ra các từ. Duyệt i từ 1 đến n:
\begin{itemize}
\item Tạo state gốc cho nút i.
\item Xét các state, nếu tiến thêm được một bước thì lưu lại state mới (i+1).
\item Nếu không tiến được thì xóa state.
\item Nếu hoàn tất một từ thì lưu lại.
\end{itemize}
\end{algo}

Sau khi hoàn tất, đánh dấu tất cả các chữ xuất hiện trong các từ tìm
được. Do từ điển không hoàn chỉnh, và do các ký hiệu, từ viết
tắt~\ldots{}{},
 sẽ có một số chữ không nằm trong bất kỳ từ nào tìm được. Do
đó ta cần duyệt lại, và đánh dấu những chữ này là từ ``UNK''. Việc tạo
thêm các từ $UNK$ sẽ đảm bảo tạo ra một đồ thị liên thông. Nếu đồ
thị không liên thông, ta không thể áp dụng thuật toán tìm đường đi
ngắn nhất.

Ngoài lưới từ cơ bản, ta có thể tạo lưới 2-từ. Lưới 2-từ
tương tự như lưới từ, tuy nhiên mỗi nút là một cặp 2 từ đi liền nhau
trong câu. Thuật toán tạo lưới 2-từ được nêu trong \cite{Ravishankar},
được tóm tắt lại như sau (xem hình~\ref{fig:wordlattice2}):

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\textwidth]{wordlattice2}
  \caption{Lưới 2-từ của câu ``Học sinh học sinh học''}
  \label{fig:wordlattice2}
\end{figure}

\begin{algo}[Tạo lưới n-từ từ lưới (n-1)-từ]
\begin{enumerate}
\item Nếu nút ($w$) có $n$ từ đứng liền trước nó ($w_i$),
  $i=1,2,\ldots{},n$ trong lưới từ gốc, nó sẽ được lặp lại $n$ lần trong
  lưới từ mới, tên là ($w_{i}w$), tương ứng với $i=1,2,\ldots{},n$.
\item Nếu ($w_i$) nối với ($w_j$) trong lưới từ gốc, nối tất cả
  ($w_xw_i$) với ($w_iw_j$) $x$ bất kỳ.
\item Giá trị của ($w_iw_j$) là giá trị của cạnh ($w_i$) ($w_j$) trong
  lưới từ cũ.
\item Giá trị của cạnh ($w_iw_j$) ($w_jw_k$) là 3-gram của $w_i$, $w_j$
  và $w_k$.
\end{enumerate}
\end{algo}

%% Các lưới n-từ có đặc điểm là tăng nhanh số nút và số cạnh, nhưng số
%% tầng vẫn không đổi (Đồ thị càng ngày càng ``mập'', nhưng ``cao''
%% không nổi ;-) )


\subsection{Lưu lưới từ}

Các nút trong lưới từ được lưu tập trung vào một mảng
(WordEntries). Truy cập nút được thực hiện thông qua index của mảng
này. Mỗi nút chứa các thông tin về từ của nút đó, bao gồm vị trí từ,
số tiếng, index trong WordEntries~\ldots{}{}

Words là một mảng tương ứng với vị trí từng tiếng trong câu. Vị trí
của mỗi tiếng sẽ được liên kết với một danh sách các từ bắt đầu tại
tiếng đó. Ta có thể coi danh sách này như danh sách các cạnh nối từ
nút đang xét đến các nút kế tiếp.


\section{Tách từ}
\label{sub:wordseg}

Dùng thuật toán tìm kiếm theo độ ưu tiên PFS\footnote{Priority-First
Search---PFS} để tìm đường đi ngắn nhất trên đồ thị. Khoảng cách giữa hai
điểm trong đồ thị là xác suất 2-gram của hai từ. Bài toán tìm đường
đi ngắn nhất, có thể áp dụng PFS, Prime, Djisktra. PFS được chọn vì
lưới từ, qua khảo sát, có thể được coi là một đồ thị thưa.

Để áp dụng 3-gram thay vì 2-gram, ta sẽ sử dụng lưới 2-từ. Sau đó áp
dụng thuật toán PFS cho đồ thị mới.

Cách làm này không thể thực hiện với n-gram ($n > 3$) vì khi đó số
nút/cạnh trong đồ thị sẽ tăng đáng kể. Ngoài ra, PFS cũng không áp
dụng được trong trường hợp sử dụng những độ đo như đo số lỗi sai đã
xảy ra~\ldots{} Trong trường hợp đó ta nên sử dụng thuật toán A*~\cite{Ravishankar}

%% XXXX. Nếu WFST cộng viterbi, beam pruning \ldots{} thì sao nhỉ?


\section{Tìm từ thay thế}

Do tiếng Việt đọc sao ghi vậy,
nên bước chuyển từ từ sang âm có thể bỏ qua. Bước còn lại là áp dụng
thuật toán đo độ hiệu chỉnh giữa hai từ như đã nêu trong~\ref{algo:ed}
Ta có thể so sánh từng ký tự, hoặc so sánh theo âm (ví dụ, ``th'' thay
vì ``t'' và ``h'').

Chương trình sẽ liệt kê XXXX (chọn theo tiêu chí nào?, 10 từ lớn nhất
hay sao đây)

XXXX. thuật toán tính ed.

\section{Giao tiếp với người dùng}
\label{sec:ui}

Cố gắng khai thác tri thức của người sử dụng, nhằm bổ trợ cho trình
bắt lỗi, giảm thiểu các sai sót do trình bắt lỗi gây ra.

Hỏi người dùng càng nhiều càng tốt. Luôn luôn có một tùy chọn ``không
biết'' cho người dùng.

\begin{itemize}
\item Phần bắt lỗi tiếng.
\item Nhận dạng từ sai.
\item Nhận dạng ký hiệu, tên riêng nước ngoài.
\end{itemize}

Sau mỗi lần sữa lỗi, cần chạy lại thuật toán để loại tác động của lỗi
sai.

Văn bản xử lý được phân thành nhiều tầng:
\begin{enumerate}
\item Văn bản thô toàn bộ. Chuỗi các ký tự.
\item Văn bản thô (câu).
\item Dạng token. Tách ra từng chuỗi con.
\item Dạng sentence. Một số token sẽ được gán id. Một số khác bị bỏ
  qua. 
\item Dạng lattice. Đồ thị các id (có thể giống hoặc khác với id ở cấp
  sentence) và các liên kết. 
\item Dạng segmentation. chuỗi id nhất định.
\end{enumerate}

Hiện tại, việc thay đổi thông tin ở tầng trên sẽ hủy mọi thông tin ở
tầng bên dưới.

Lưu lại các thông tin của người dùng như thế nào? Các thông tin này là
``global'' hay ``local''?

\section{Trình huấn luyện}
\label{sec:training}

\subsection{Tiền xử lý}
Giống như phần~\ref{sub:preprocess}


\subsection{Tạo Lưới từ}
Giống như phần~\ref{sub:lattice}, nhưng chỉ xét những từ nào thực sự
có trong câu, sử dụng lưới từ thay vì lưới từ mở rộng.


\subsection{Thống kê n-gram}
\label{sub:wordcount}

Nếu dùng PFS để tách từ, ta chỉ có 1 cách tách từ tốt nhất. Việc đếm
từ sẽ dựa trên cách tách từ này.

Như đã nói, có thể dùng WFST hoặc dùng thuật toán trong
\cite{softcount} (tạm gọi là thuật toán ``soft-count'') để tách
từ. WFST phải dùng kèm với beam pruning để tránh bùng nổ số tổ hợp các
cách tách từ. Sau khi dùng WFST, ta còn n cách tách từ, có thể đếm
fractional count (được đề cập bên dưới) trên các cách tách từ này.

Trường hợp nhiều cách tách từ, ta có thểm đếm từ trên tất cả các cách
tách, thay vì chỉ đếm trên cách tách từ tốt nhất. Cách này phản ánh
tầm ảnh hưởng của các từ tốt hơn. Ví dụ, ta có 3 cách tách từ với xác
suất các cách tách từ tương ứng lần lượt là 0,5, 0,4 và 0,1. Cách chỉ
dùng cách tách từ tốt nhất sẽ chỉ tính những từ trong cách tách từ
đầu, với giá trị mỗi từ là 1,0. Cách tính này ``dồn phiếu'' của 2 cách
sau cho cách đầu. Trường hợp sau, các từ trong cách 2 và 3 vẫn được
tính. Số đếm của mỗi từ không còn là 1, mà là xác suất của cách tách
từ chứa từ đó. Trở lại ví dụ, các từ trong cách một sẽ được cộng thêm
0,5 thay vì 1. Ngoài ra các từ trong cách 2 và 3 lần lượt được cộng
0,4 và 0,1. Dễ thấy, các từ trong cách tách từ thấp sẽ không tăng số
đếm đáng kể, do đó không thể gây ảnh hưởng lớn đến quyết định tách từ.
Cách cộng dồn số như vậy được gọi là ``fractional count'' (hay trong
\cite{softcount} gọi là ``soft-count'').

Luận văn này thuật toán soft-count để đếm mọi cách tách từ. Soft-count
thực tế không kết xuất ra một cách tách từ cụ thể nào (và do vậy nên
cũng không thể áp dụng để tìm cách tách từ tốt nhất được!). Thay vào
đó, thuật toán đếm mọi từ thể có. Thuật toán được mô tả trong
\cite{softcount} không dùng từ điển. Mọi chuỗi con trong câu đều được
cho là từ. Điểm này, vừa là điểm mạnh vì không cần dùng từ
điển, nhưng cũng là điểm yếu vì yếu tố này làm giảm độ chính xác một
cách đáng kể (khoảng 20\%, như kết quả trong \cite{softcount}).

Giả sử câu S có $n$ tiếng, $2^{n-1}$ cách tách từ khác nhau, xác suất
mỗi cách tách từ là $p(1),p(2),\ldots{},p(n)$.
Với mỗi từ trong một cách tách từ, ta cộng thêm một khoảng
$\displaystyle\frac{p(i)}{\sum_{i=1}^n{p(i)}}$ cho từ đó. Soft-count dùng
lập trình quy hoạch động để thực hiện quá trình này.

Thuật toán được dùng ở đây là thuật toán soft-count, được hiệu chỉnh
sử dụng từ điển và lưới từ để hạn chế những từ không phải là từ.

Cho lưới từ của câu S. Gọi $L(W)$ là tập những từ nối đến nút
$W$. Tương tự, $R(W)$ là tập những từ được nối đến từ nút $W$.
Với mỗi nút $W$ trong S, tổng xác suất các cách tách từ có chứa nút
$W$ là:
$$P(W)=P^{left}(W)p(W)P^{right}(W)$$
Trong đó:
\begin{itemize}
\item $P^{left}(W)$ là tổng xác suất các cách tách từ tính từ đầu câu
  đến $W$.
\item $P^{right}(W)$ là tổng xác suất các cách tách từ tính từ $W$ đến
  hết câu.
\end{itemize}

$$
P^{left}(W) = \left\{
    \begin{array}{ll}
      p(W)&\text{nếu W là nút head}\\
      \displaystyle\sum_{W' \in L(W)}p(W')P^{left}(W')&\text{ngược lại}\\
    \end{array}
  \right.
$$

Tương tự

$$
P^{right}(W) = \left\{
    \begin{array}{ll}
      p(W)&\text{nếu W là nút tail}\\
      \displaystyle\sum_{W' \in R(W)}p(W')P^{right}(W')&\text{ngược lại}\\
    \end{array}
  \right.
$$

\begin{algo}[Tính $P^{left}$]
\begin{enumerate}
\item Đặt $P^{left}(head) = p(head)$
\item Đặt $P^{left}(W) = 0$ với mọi $W$ còn lại.
\item Duyệt lần lượt các nút $W$ theo thứ tự từ trái sang phải, tính
  theo vị trí bắt đầu của $W$ trong câu. Với $W' \in R(W)$
  cộng thêm $p(W)P^{left}(W)$ vào $P^{left}(W')$
\end{enumerate}
\end{algo}

Thuật toán tương tự được áp dụng để tính $P^{right}$.

Sau khi tính được $P^{left}$ và $P^{right}$, ta có thể tính fractional
count cho các từ trong câu bằng cách duyệt tất cả các nút trong lưới từ,
cộng thêm vào $\displaystyle\frac{P(W)}{P^{left}(tail)}$ cho từ
$C$. Thực tế, ta sẽ lồng bước này vào trong thuật toán tính
$P^{right}$, vì thuật toán cũng phải duyệt qua tất cả các từ.

\begin{algo}[Tính $P^{right}$]
\begin{enumerate}
\item Đặt $P^{right}(tail) = p(tail)$
\item Đặt $P^{right}(W) = 0$ với mọi nút còn lại.
\item Duyệt tất cả các nút $W$ từ phải sang trái, tính theo vị trí kết
  thúc của $W$ trong câu.
  \begin{enumerate}
  \item Với $W' \in L(W)$, cộng thêm $p(W)P^{right}(W)$ vào
    $P^{right}(W')$
  \item Tính fractional count cho $W$ theo công thức
    $\displaystyle\frac{P^{left}(W)p(W)P^{right}(W)}{P^{left}(tail)}$
  \end{enumerate}
\end{enumerate}
\end{algo}


Tuy nhiên, thuật toán trên (cũng như thuật toán gốc) sử dụng
uni-gram, trong khi trình bắt lỗi lại dùng 2-gram. Để cho phép thuật
toán dùng 2-gram, ta có thể tạo một lưới 2-từ như cách của
\cite{Ravishankar} khi muốn tách từ dựa trên 3-gram. Tuy nhiên, để áp
dụng cách này với 3-gram đòi hỏi phải tạo lưới 3-từ! Số lượng nút
trong lưới 3-từ nhiều hơn nhiều so với lưới từ gốc, làm giảm tính hiệu
quả của thuật toán. 

Thay vì vậy, thuật toán được hiệu chỉnh để áp dụng 2-gram với lưới từ
thông thường. Thay vì dùng giá trị nút để tính, ta dùng giá trị cạnh
để tính. $p(W)$ sẽ được thay bằng $p(W/W')$.

$$P(W)=P^{left}(W)P^{right}(W)$$

$$
P^{left}(W) = \left\{
    \begin{array}{ll}
      p(W)&\text{nếu W là nút head}\\
      \displaystyle\sum_{W' \in L(W)}p(W/W')P^{left}(W')&\text{ngược lại}\\
    \end{array}
  \right.
$$

Tương tự

$$
P^{right}(W) = \left\{
    \begin{array}{ll}
      p(W)&\text{nếu W là nút tail}\\
      \displaystyle\sum_{W' \in R(W)}p(W'/W)P^{right}(W')&\text{ngược lại}\\
    \end{array}
  \right.
$$

$P(W)$ đại diện cho xác suất tất cả các cách tách từ đi qua nút
$W$. Do ta huấn luyện 2-gram, nên cần xác suất $P(W/W')$ chứ không cần
$P(W)$. Nếu $W$ và $W_{+1}$ chỉ có một cạnh, $P(W)$ cũng chính là
$P(W/W_{+1})$. Nếu có nhiều hơn một cạnh, ta cần dùng cách khác để
tính $P(W/W')$. Với thuật toán tính $P^{right}$ hiện có, ta cộng dồn
$p(W/W')P^{right}$ vào cho $P^{right}(W)$. Vậy trong quá trình cộng
dồn ta có thể tính ngay $P(W/W')$ bằng cách nhân giá trị cộng dồn với
$P^{left}(W)$. Thuật toán tính $P^{left}$ và $P^{right}$ sau cùng như
sau:

\begin{algo}[Tính $P^{left}$]
\begin{enumerate}
\item Đặt $P^{left}(head) = p(head)$
\item Đặt $P^{left}(W) = 0$ với mọi $W$ còn lại.
\item Duyệt lần lượt các nút $W$ theo thứ tự từ trái sang phải, tính
  theo vị trí bắt đầu của $W$ trong câu.
  Với mỗi $W$ tìm được, cộng thêm $p(W'/W)P^{left}(W)$ vào $P^{left}(W')\quad
  W' \in R(W)$
\end{enumerate}
\end{algo}

\begin{algo}[Tính $P^{right}$]
\begin{enumerate}
\item Đặt $P^{right}(tail) = p(tail)$
\item Đặt $P^{right}(W) = 0$ với mọi nút còn lại.
\item Duyệt tất cả các nút $W$ từ phải sang trái, tính theo vị trí kết
  thúc của $W$ trong câu. Với $W' \in L(W)$:
  \begin{enumerate}
  \item Cộng thêm $p(W/W')P^{right}(W)$ vào $P^{right}(W')$
  \item Tính fractional count cho $W'$ theo công thức
    $\displaystyle\frac{P^{left}(W')p(W/W')P^{right}(W)}{P^{left}(tail)}$
  \end{enumerate}
\end{enumerate}
\end{algo}

Với cách tính này, ta có thể dùng lưới từ cùng với 2-gram. Để tính
3-gram, ta dùng lưới 2-từ. 

\subsection{Tính n-gram}

N-gram được tính như thông thường. Sử dụng backoff chuẩn. Thư viện
SRILM được dùng để tính n-gram.




\chapter{Cài đặt}
\label{cha:implementation}
\minitoc

Chương trình gồm hai phần: phần bắt lỗi chính tả và phần huấn luyện.

\section{Trình bắt lỗi chính tả}



\section{Cấu trúc dữ liệu}


\subsection{Lưu chuỗi}

Để giảm thiểu không gian bộ nhớ, chương trình không thao tác trực tiếp
trên các chuỗi mà lưu tập trung các chuỗi lại, sau đó dùng mã id để
đánh số từng chuỗi một. Các thao tác so sánh sẽ dựa trên id này. Khi
cần thao tác trên chuỗi, ta sẽ thông qua id để lấy chuỗi gốc.

Các chuỗi được lưu trong một associative array và một array. Một dùng
để ánh xạ chuỗi sang id. Một để ánh xạ id sang chuỗi.

Có thể dùng lexical tree để giảm thiểu không gian lưu chuỗi (UNIMPL)

Mỗi chuỗi có thể có nhiều id: id gắn với chuỗi gốc ({\em id}), id gắn
với chuỗi gốc đã chuẩn hoá ({\em sid}), id gắn với chuỗi viết thường
({\em cid}), id  gắn với chuỗi viết thường đã chuẩn hoá ({\em
  scid}). Các id này giúp việc so sánh được dễ dàng hơn. 

Trong hầu hết quá trình hoạt động, {\em sid} sẽ được dùng. Tuy nhiên,
cũng có khi sẽ dùng {\em scid}. Bởi vậy, mỗi chuỗi sẽ có một id khác
là {\em fid}, hoặc bằng {\em sid}, hoặc bằng {\em scid}~\ldots{}{} {\em
  fid} sẽ được dùng trong hầu hết các hoạt động, trừ phần tiền xử lý.

Mỗi từ sẽ chỉ lưu id và fid.

\subsection{Lưu từ điển}

Từ điển được lưu thành một cấu trúc dạng cây. Hiện tại từ điển lưu các
từ gốc đã chuẩn hoá, và các từ viết thường đã chuẩn hoá.

Với bản huấn luyện, lưu thêm id gốc để có thể xuất ra y như cũ ??
Không cần. Wordlist sẽ lưu theo dạng chuẩn hoá. Như vậy không cần lưu
id gốc. Quá trình training cần có bước chuyển tiếp để đọc wordlist
chưa chuẩn hoá, ghi ra wordlist chuẩn hoá.


\section{Dữ liệu huấn luyện}
\label{sec:data-preprocessing}

Dữ liệu gốc bao gồm: danh sách từ và các văn bản tiếng Việt thu thập
từ mạng VnExpress\footnote{http://www.vnexpress.net}.

Nhiệm vụ:
\begin{itemize}
\item Tạo danh sách tiếng, chuẩn hoá danh sách tiếng.
\item Tiền xử lý ngữ liệu.
\item Huấn luyện n-gram, tạo ra dữ liệu n-gram.
\end{itemize}


\subsection{Dữ liệu nguồn}
\label{sec:data-source}

Dữ liệu nguồn bao gồm danh sách từ và ngữ liệu tiếng Việt. Dữ liệu
được lưu dưới dạng mã VISCII. 
\subsubsection{Danh sách từ}

Đây là một tập tin văn bản lưu tất cả các từ được dùng trong tiếng
Việt, mỗi từ một dòng. Các chữ cách bởi một khoảng trắng.


\subsubsection{Ngữ liệu huấn luyện}

Bao gồm một loạt các tập tin văn bản tiếng Việt. Mỗi dòng là một đoạn
văn bản.

\subsection{Danh sách tiếng}
\label{sub:syllable-list}

Danh sách tiếng chứa mọi tiếng thông dụng nhất được sử dụng trong
tiếng Việt. Danh sách này được rút trích từ danh sách từ, sau đó được
lưu ở dạng chuẩn hoá.

Danh sách tiếng được rút trích tự động khi chương trình nạp danh sách
từ.

%Chương trình syllable-extract được dùng để tạo danh sách này. Cách
%dùng:
%\begin{verbatim}
%$syllable-extract < word-list > syllable-list
%\end{verbatim}


\subsection{Tiền xử lý ngữ liệu huấn luyện}
\label{sec:training-data-preprocessing}

Dữ liệu thu được từ VnExpress bao gồm một loạt các file html, chia
thành nhiều thư mục.

htmltidy được sử dụng để chuyển dữ liệu html về dạng xhtml. Các file
html của VnExpress không hoàn toàn tuân theo chuẩn html, bao gồm hai
trường hợp:

\begin{itemize}
\item Sử dụng tag <vne>
\item Không đóng tag <frame>
\end{itemize}

Hai lỗi này được tự động phát hiện và sửa chữa trước khi chuyển dữ
liệu cho htmltidy.

Sau khi chạy htmltidy, ta được dữ liệu xhtml hợp khuôn dạng. Phân tích
các tài liệu này cho thấy phần nội dung chính thường nằm trong tag
<vne>, hoặc trong tag <table> với thuộc tính id là
``CContainer''. XSLT được sử dụng để lọc ra phần nội dung nằm giữa hai
tag này (\verb#z.xslt#).

Trình \verb#convert.sh# sẽ thực hiện bước htmltidy và xslt ở trên. Cách sử
dụng:
\begin{verbatim}
$convert.sh < input  > output
\end{verbatim}

Sau bước này, ta cần lọc bỏ các tag, loại bỏ các entity~\ldots{}{} để
đưa dữ liệu về dạng văn bản thuần túy. Do số lượng tag được định nghĩa
html rất nhiều nên chỉ xử lý những tag nào được sử dụng trong
VnExpress (thông qua chương trình \verb#gettags.pl#). Các tag này được loại
bỏ bằng \verb#html2text.pl#. Các mã utf-8 được sử dụng trong
VnExpress (thông qua chương trình \verb#z.c#) được chuyển về mã VISCII
qua \verb#z.cpp#. Các entity còn lại (lấy bằng \verb#list-entity.pl#)
được xử lý trong \verb#html2text.pl#.

\verb#html2text.pl# sử dụng các tag để tách dữ liệu thành các đoạn. Dữ
liệu sau cùng là các tập tin văn bản, mỗi dòng là một đoạn.

\subsection{Huấn luyện dữ liệu}
\label{sub:training-data}

Chương trình \verb#wfst-train# được dùng để huấn luyện dữ liệu. Thông
tin nhập là danh sách từ, danh sách tiếng, n-gram (nếu có). Thông tin
xuất là n-gram mới.

Chương trình được lặp đi lặp lại nhiều lần.

\chapter{Đánh giá và kết luận}
\label{cha:conclusion}
\minitoc

\section{Hạn chế}
\begin{itemize}
\item Không sử dụng những thông tin cấp cao hơn.
\item Có khả năng nó tự động sửa từ đúng thành từ sai, do từ sai
  ``hay'' được dùng trong câu đó hơn là từ đúng :-P
\end{itemize}

\section{Hướng phát triển}
\label{sec:todo}

Viết lại từ đầu :-D

\begin{itemize}
\item Các hướng cải tiến EM.
\item Tư tưởng cơ bản hiện thời là phát sinh mọi trường hợp tương tự
  với trường hợp đang xét và hy vọng giải pháp đúng cũng nằm trong
  đó. Cách này có hai điểm cần bàn:
  \begin{itemize}
  \item Khi nào nên phát sinh, khi nào không? Nói cách khác, khi nào
    ta ``cảm thấy'' chỗ đó có thể bị sai? Statistics/Genetic approach?
  \item Khi phát sinh, nên đánh giá tầm quan trọng của các cách phát
    sinh  cho hợp lý, không nên đánh đồng như hiện nay. How can i do
    that? 
  \end{itemize}
\item Ngoài cách đang làm, còn hướng nào khác không? Liệu speech
  recognition/OCR có ý kiến nào hay không? Cần tìm hiểu mọi thứ liên
  quan đến ``error tolerance''
\item \verb#Syllable::to_str()# output sai từ ``của''.
\item Từ điển bao gồm hai loại viết hoa ``Việt Nam'' và ``A di đà
  phật''. Nên phát sinh thêm loại ``A Di Đà Phật'' luôn. Làm sao chuẩn
  hoá cả hai càng tốt. Chỉ cần lưu ``a di đà phật'' là đủ.
\item \verb#Syllable::parse()# sẽ gặp vấn đề với chữ hoa.
\end{itemize}

\appendix
\chapter{Blah}

\bibliographystyle{alpha}
\bibliography{reference}

%% \begin{thebibliography}{}
%% \bibitem{Ravishankar}Mosur K. Ravishankar. 1996. {\em Efficient Algorithms for
%%   Speech Recognition.} PhD thesis. %CMU-CS-96-143.ps
%% \bibitem{Oflazer}Kemal Oflazer. 1996. {\em Error-tolerant Finite State
%%   Recognition with Applications to Morphological Analysis and Spelling
%%   Correction.} %oflazer96errortolerant.ps.gz
%% \bibitem{LAH}Le An Ha. {\em A method for word segmentation in
%%   Vietnamese.} %Ha-03.pdf
%% \bibitem{Chang}Chao-Huang Chang. {\em A New Approach for
%%   Automatic Chinese Spelling Correction.} %a-new-approach-for.ps
%% \bibitem{Sproat}Richard Sproat, William Gale, Chilin Shih, Nancy
%%   Chang. {\em A Stochastic Finite-State Word-Segmentation Algorithm for
%%   Chinese.} ACL Vol 22 N3.%J96-3004.pdf
%% \bibitem{Chunyu}Chunyu Kit, Zhiming Xu, Jonathan
%%   J. Webster. {\em Integrating Ngram Model and Case-based Learning For
%%   Chinese Word Segmentation.}%tsdx.ps.gz
%% \bibitem{softcount}Xianping Ge, Wanda Pratt,
%%   Padhraic Smyth. {\em Discovering Chinese Words from Unsegmented
%%   Text.}%mlwordsigir.ps
%% \bibitem{text-tiling}Jianfeng Gao, Hai-Feng Wang, Mingjing Li, Kai-Fu
%%   Lee. {\em A Unified Approach to Statistical Language Modeling for
%%   Chinese.}%icassp00.pdf
%% \bibitem{}Nianwen Xue.{\em Chinese Word Segmentation as Character
%%   Tagging.}%paper2.pdf
%% \bibitem{self-supervised}Fuchun Peng and Dale Schuurmans. {\em Self-Supervised Chinese
%%   Word Segmentation.}%IDA01.pdf
%% \bibitem{phonetex}Victoria J. Hodge, Jim Austin. {\em An Evaluation of
%%   Phonetic Spell Checkers}%an-evaluation-of-phonetic.ps.gz
%% \bibitem{soundex}K. Kukich. 1992. {\em Techniques for Automatically Correcting
%%   Words in Text.}
%% \bibitem{}Cláudio L. Lucchesi and Tomasz Kowaltowski. {\em Applications of
%%   Finite Automata Representing Large Vocabularies.}%lucchesi92applications.ps.gz
%% \bibitem{}Bo-Hyun Yun, Min-Jeung Cho, Hae-Chang Rim. {\em Segmenting Korean
%%   Compound Nouns using Statistical Information and a Preference
%%   Rule. }%PACLING97.ps 
%% \bibitem{}Roger I. W. Spooner and Alistair D. N. Edwards. {\em User
%%   Modelling for Error Recovery: A Spelling Checker for Dyslexic
%%   Users}%spooner97user.ps.gz 
%% \bibitem{}Theppitak Karoonboonyanan, Virach Sornlertlamvanich,
%%   Surapant Meknavin. {\em A Thai Soundex System for Spelling Correction.}%tsdx.ps.gz
%% \bibitem{}Justin Zobel and Philip Dart. {\em Finding Approximate Matches in
%%   Large Lexicons.}%zobel95finding.ps.gz
%% \bibitem{}Sun Maosong, Shen Dayang, Huang Changning. {\em CSeg\&Tag1.0: A
%%   Practical Word Segmenter and POS Tagger for Chinese Texts.}%A97-1018.pdf
%% \bibitem{wordseg}Đinh Điền, Hoàng Kiếm, Nguyễn Văn Toàn. {\em Vietnamese Word
%%   Segmentation.}%0047-02.pdf
%% \bibitem{}Bidyut Baran Chaudhuri. {\em Reversed word dictionary and
%%   phonetically similar word grouping based spell-checker to Bangla
%%   text.}%bangla.pdf
%% \bibitem{}Timothy Gambell, Charles D. Yang. {\em Scope and Limits of
%%   Statistical Learning in Word Segmentation.}%gambell_yang.pdf
%% \bibitem{iccc}Andi Wu, George Heidorn, Zixin Jiang, Terence
%%   Peng. {\em Correction of Erroneous Characters in Chinese Sentence
%%   Analysis.}%ICCC-2001.pdf
%% \bibitem{}Fuchun Peng, Xiangji Huang, Dale Schuurmans, Shaojun
%%   Wang. {\em Text Clasification in Asian Languages without Word
%%   Segmentation.}%IRAL2003.pdf 
%% \bibitem{}Yalin Wang, Ihsin T. Phillips, Robert
%%   Haralick. {\em Statistical-based Approach to Word Segmentation.}%wordicpr.pdf
%% \bibitem{}{\em Combining Syntactical And Statistical Language Constraints
%%   in Context-dependent Language Models for Interactive Speech
%%   Applications.}%K026.pdf
%% \bibitem{LoiChinhTa}TS. Lê Trung Hoa. 2002. {\em Lỗi chính tả và cách khắc phục. NXB Khoa
%%   học Xã hội.} 
%% \bibitem{LoiTuVung}PGS. Hồ Lê, TS. Trần Thị Ngọc Lang, Tô Đình Nghĩa. 2002. {\em Lỗi từ
%%   vựng và cách khắc phục.} NXB Khoa học Xã hội.
%% \bibitem{Tuoi}PTS. Phan Thị Tươi, KS. Nguyễn Hứa Phùng, KS. Huỳnh Vụ
%%   Như Liên, KS. Phạm Quyết Thắng. 1998. {\em Bắt lỗi chinh tả tự động cho
%%   tiếng Việt bằng máy tính.}
%% \bibitem{worddef}Đinh Điền. 2000. {\em Từ tiếng Việt.} VNU-HCMC.
%% \bibitem{}Andrew R. Golding. 1995. {\em A Bayesian hybrid method for
%%     context-sensitive spelling correction}. Proceedings of the Third
%%     Workshop on Very Large Corpora, pages 39-53.
%% \bibitem{}Andrew R. Golding and Dan Roth. 1999. {\em A Winnow-based
%%     approach to context-sensitive correction}. Machine Learning,
%%     Special issue on Machine Learning and Natural Language Processing,
%%     34:107-130.
%% \bibitem{}Andrew R. Golding and Yves Schabes. 1996. {\em Combining
%%     trigram-based and feature-based methods for context-sensitive
%%     spelling correction}. Proceedings of the 34th Annual Meeting of
%%     the Association for Computational Linguistics.
%% \end{thebibliography}


\end{document}


Giả sử câu S có $n$ tiếng $c_1,c_2,\ldots{},c_n$, có $|S|$ cách tách từ
$S_1,S_2,\ldots{},S_{|S|}$ và cách tách từ  $S_i$ được
tách thành $|S_i|$ từ $W_{i_1},W_{i_2},\ldots{},W_{i_{|S_i|}}$ với 
$W_i$ là một từ xác định bắt đầu ở tiếng thứ $i$ chứa $|W_i|$ tiếng, và
$i_j$ là vị trí từ thứ $j$ trong cách tách câu $i$.

Ta có:
$$p(i)=\sum_{j=1}^{|S_i|}{p(W_{i_j})}$$

Một câu sẽ được tách thành:
$$P(W_i) = P_{i}^{left}p(W_{i})P_{i+|W_i|}^{right}$$

$P_i^{left}$ là xác suất tất cả các tổ hợp từ có thể có từ 
tiếng thứ nhất đến tiếng thứ $i$.

$P_{i}^{right}$ là xác suất tất cả các tổ hợp từ có thể có từ tiếng
thứ  $i$ đến hết câu. 

Dễ thấy, với mỗi từ $C$ trong câu $S$, fractional count W của từ sẽ là
$\displaystyle\frac{P(W)}{\sum_i^{|S|}p(i)}$.

$\displaystyle\sum_i^{|S|}p(i)$ cũng chính là $P_{n+1}^{left}$ theo
định nghĩa $P_i^{left}$.

Ta sẽ dùng quy hoạch động để tính $P_i^{left}$ và $P_i^{right}$

$$
P_i^{left} = \left\{
  \begin{array}{lr}
    1 & i=1\\
    p(W_i) & i=2\\
    \sum_{j=1}^{i-1}p(c_j\ldots{} c_{i-1})P_j^{left} & i>2
  \end{array}
\right.
$$

$$
p(c_i\ldots{} c_j) = \left\{
  \begin{array}{ll}
    p(W_i)&\text{nếu } c_i\ldots{} c_j \text{ tạo thành } W_i\\
    0&\text{ngược lại}
  \end{array}
\right.
$$

Thuật toán tính $P^{left}$ như sau:
\begin{enumerate}
\item Đặt $P_1^{left} = 1$
\item Đặt $P_i^{left} = 0\quad \forall i \in [2\ldots{} n+1]$
\item Duyệt i từ 1 đến n, tìm tất cả các từ $W_i$ (do tại có thể có
  nhiều từ bắt đầu tại tiếng $i$).
  Với mỗi từ $W_i$ tìm được, cộng thêm $p(W_i)$ vào $P_{i+|W_i|}^{left}$
\end{enumerate}

Thuật toán tương tự được áp dụng để tính $P^{right}$.

Sau khi tính được $P^{left}$ và $P^{right}$, ta có thể tính fractional
count trong câu bằng cách duyệt tất cả các từ có thể có trong câu,
cộng thêm vào $\displaystyle\frac{P(W)}{P_{n+1}^{left}}$ cho từ
$C$. Thực tế, ta sẽ lồng bước này vào trong thuật toán tính
$P^{right}$, vì thuật toán cũng phải duyệt qua tất cả các từ.

Vậy thuật toán tính $P^{right}$ là:
\begin{enumerate}
\item Đặt $P_{n+1}^{right} = 1$
\item Đặt $P_i^{right} = 0\quad \forall i \in [1\ldots{} n]$
\item Duyệt i từ n+1 đến 1.
  \begin{enumerate}
  \item tìm tất cả các từ $W_j$ sao cho $j+|W_j|=i$.
    Với mỗi từ $W_j$ tìm được, cộng thêm $p(W_j)$ vào
    $P_j^{right}$
  \item Tính fractional count cho tất cả các từ $W_i$ ($i \le n$)
  \end{enumerate}
\end{enumerate}


Ví dụ: câu ``học sinh học sinh học'' có 8 cách tách từ
\begin{verbatim}
học-sinh học-sinh học
học-sinh học sinh học
học-sinh học sinh-học
học sinh học sinh học
học sinh học sinh-học
học sinh học-sinh học
học sinh-học sinh học
học sinh-học sinh-học
\end{verbatim}
\def\Zhs{\text{học-sinh}}
\def\Zsh{\text{sinh-học}}
\def\Zh{\text{học}}
\def\Zs{\text{sinh}}
Ta có
$$
\begin{array}{rl}
P_1^{left}(\Zhs) &= p(\Zhs_1/\phi)\\
P_1^{left}(\Zh) &= p(\Zh_1/\phi)\\
P_2^{left}(\Zs) &= p(\Zs_2/\Zh_1)P_1^{left}(\Zh)\\
 &=p(\Zs_2/\Zh_1)p(\Zh_1/\phi)\\
P_2^{left}(\Zsh) &= p(\Zsh_2/\Zh_1)P_1^{left}(\Zh)\\
 &=p(\Zsh_2/\Zh_1)p(\Zh_1/\phi)\\
P_3^{left}(\Zhs) &= p(\Zhs_3/\Zhs_1)P_1^{left}(\Zhs)+p(\Zhs_3/\Zs_2)P_2^{left}(\Zs)\\
 &=p(\Zhs_3/\Zhs_1)p(\Zhs_1/\phi)+p(\Zhs_3/\Zs_2)p(\Zs_2/\Zh_1)p(\Zh_1/\phi)\\
 &=p(\Zhs_1,\Zhs_3)+p(\Zh_1,\Zs_2,\Zhs_3)\\
P_3^{left}(\Zh) &= p(\Zh_3/\Zs_2)P_2^{left}(\Zs)+p(\Zh_3/\Zhs_1)P_1^{left}(\Zhs)\\
 &=p(\Zh_3/\Zs_2)p(\Zs_2/\Zh_1)p(\Zh_1/\phi)+p(\Zh_3/\Zhs_1)p(\Zhs_1/\phi)\\
 &=p(\Zh_1,\Zs_2,\Zh_3)+p(\Zhs_1,\Zh_3)\\
\end{array}
$$

$$
\begin{array}{rl}
P_5^{right}(\Zh) &= p(\Phi/\Zh_5)\\
P_4^{right}(\Zsh) &= p(\Phi/\Zsh_4)\\
P_4^{right}(\Zs) &= p(\Zh_5/\Zs_4)P_5^{right}(\Zh)\\
 &=p(\Zh_5/\Zs_4)p(\Phi/\Zh_5)\\
P_3^{right}(\Zh) &= p(\Zsh_4/\Zh_3)P_4^{right}(\Zsh)+p(\Zs_4/\Zh_3)P_4^{right}(\Zs)\\
 &=p(\Zsh_4/\Zh_3)p(\Phi/\Zsh_4)+p(\Zs_4/\Zh_3)(\Zh_5/\Zs_4)p(\Phi/\Zh_5)\\
 &=p(\Zh_3,\Zsh_4)+p(\Zh_3,\Zs_4,\Zh_5)\\
P_3^{right}(\Zhs) &= p(\Zh_5/\Zhs_3)P_5^{right}(\Zh)\\
 &=p(\Zh_5/\Zhs_3)p(\Phi/\Zh_5)\\
 &=p(\Zhs_3,\Zh_5)\\
\end{array}
$$

$$
\begin{array}{rl}
P_3(\Zhs) &= P_3^{left}(\Zhs)P_3^{right}(\Zhs)\\
 &=[p(\Zhs_1,\Zhs_3)+p(\Zh_1,\Zs_2,\Zhs_3)]p(\Zhs_3,\Zh_5)\\
 &=p(\Zhs_1,\Zhs_3)p(\Zhs_3,\Zh_5)+p(\Zh_1,\Zs_2,\Zhs_3)p(\Zhs_3,\Zh_5)\\
 &=p(\Zhs_1,\Zhs_3,\Zh_5)+p(\Zh_1,\Zs_2,\Zhs_3,\Zh_5)
\end{array}
$$