\documentclass[a4paper]{jsarticle}

\usepackage{tani_resume}%�X�^�C���t�@�C���̓ǂݍ���

\alignbeforeskip -5mm
\alignafterskip -5mm
\eqnarraybeforeskip -5mm
\eqnarrayafterskip -5mm

%jp�͓��{��
%e�͉p��
%title��author�͎����p�ɏ��������Ă��������B
\setcounter{page}{23}
\jptitle{���C�X������p���������̕������ɂ���}
\etitle{Automated classification of dialect that uses rice code}
\jpauthor{�v�c�@�^���Y}
\eauthor{Shintaro Masuda}
\course{�J�@������}
\year{21}
\abstract{%�T�v(2009�����o�[�͏����Ă��܂��B)
%��������
���k�Ɋ�Â����f�[�^�Ԃ̗ގ��x�Ɋւ��鋗������`����ADNA �̗ގ��x�⌾��̗ގ��x�A���y�̗ގ��x����ɗL�p�ł���Ƃ����������ʂ������Ă���B
�ߔN�A�J�������ł͈��k�ގ��x��p���������̎������ނ��s���Ă����B�{�����ł͕����f�[�^�ɂ����āA�����𐔒l�ɒu�������ĒP���������f�[�^��
����Ƀ��C�X���������邱�Ƃ��Ă���B�{��Ă����ނ̐��x�̌���ɗL�������m���߂邽�߁A��̓I�Ȏ�����������B
%�����܂ŊT�v
}


\begin{document}%�h�L�������g�̎n��

\maketitle

\begin{multicols}{2}%���͂�2�i���ɕ����違���͂̎n��

\section{�͂��߂�}

%�w�i�E���@�E��s�����E�ړI�E�����邱�Ƃ����̉��ɁB
���ݗl�X�Ȏ������f�[�^������Ă���B�������A��
�y�╶�͂��u�f�[�^�v�Ƃ��Ĉ�����悤�ɂȂ��Ă��Ă�
��BMing Li �炪���k�ގ��x�Ɋ�Â��f�[
�^�Ԃ̗ގ��x�Ɋւ��鋗����\��similarity metric ��
�āi����DNA �̗ގ��x�⌾��̗ގ��x�A���y�̗ގ��x��
��ɗL�p���Ƃ������Ƃ��������Ă���B�j�����B[1]
�܂��A���k�ގ��x�����̓f�[�^���������قǂ��ߎ������B\\
�J�������ł́A���k�ގ��x��p���������̎������ނɂ��Č������Ă���B
��s�����ł́A�����̉����f�[�^���e�L�X�g�����A�����āA�O�����������Đ��l�����Ă����B[2]
�{�����ł́A�]���̑O�����Ő��l�����ꂽ�f�[�^�𕄍�������Ƃ����V���ȑO�������s���B
����������ɂ�����A�������ȒP�ŉ摜�≹���̈��k�A���S���Y���̒��ł悭�g���Ă��郉�C�X�������g�����Ƃɂ���B[3]
�{�����ł́A���C�X�������ɂ��f�[�^���������Ȃ邩�m���߂邽�߁A�]���̑O�������{�����f�[�^�ƐV���ɏ]���̑O�������{�����f�[�^�Ƀ��C�X���������{�����f�[�^�Ƃ�
�t�@�C���T�C�Y��r���s���B�Ȃ��A�O�������{�����f�[�^�͈��k���{�����ꍇ�ƈ��k���{���ĂȂ��ꍇ��2�p�^�[���Ńt�@�C���T�C�Y��r���s���B
���k���@�Ɋւ��ẮA��s�����ŗǂ����ʂ��o�Ă���bzip2���g���B\\
��Q�͂ł͈��k�ގ��x�ɂ��āA��3�͂ł̓��C�X�����ɂ��āA��4�͂ł͎����f�[�^�A�����T�v�A��5�͂ł͎������ʁA�l�@�A��6�͂ł͍���̉ۑ���q�ׂ�B

%�����܂Ł@�͂��߂�


\section{���k�ގ��x}
%���̂��߂̏����i�ǂސl�^�����l�̂��߁j�@�����̉���

���w�ɂ����ċ�����ԂƂ́C�C�ӂ�2 �_�Ԃŋ�������
�߂�ꂽ��Ԃ̂��Ƃ������B\\
\fbox{��`}\\
����W��$X$ ��̋����Ƃ́C�����l�֐�$d : X \times X \rightarrow R $
�ŔC�ӂ�$x, y, z \in  X $�ɑ΂��Ď��̂悤�Ȑ����𖞂����B
\[ d(x, y) \geq 0 \]
\[ d(x, y) = 0 \Leftrightarrow x = y \]
\[ d(x, y) = d(y, x)  \]
\[ d(x, y) \leq d(x, z) + d(z, y) : �O�p�s���� \]
��������ƂɁC��񋗗��ɂ��čl����B
Ming Li,Xin Chen ��̌����ł́C���Ɋւ��鋗��
��W�������Ă���, �C�ӂ̕�����x; y �ɂ��āC�ȉ���
�悤�Ɍ��߂Ă���B
\[d(x,y) =  \frac{max \{K(x|y),K(y|x) \}}{max \{K(x),K(y) \}} \]
�܂��C$K(y) \geq K(x)$�Ƃ����Ƃ��C
\[d(x,y) = \frac{K(y|x)}{K(y)} \]
����ɑ΂��ď��ʂ̌�����p����ƁC
\[d(x,y) = \frac{K(y) - I(x:y)}{K(y)} \]
�ƂȂ�B�܂��C$O(logK(xy))$ �͈̔�
�ł�$K(xy) = K(x) + K(y|x)$ �����藧�̂ŁC
\[d(x,y) = \frac{K(xy) - K(x)}{K(y)} \]
�ƕ\�����Ƃ��ł���B\\
kolmogorov �L�q�ʂ͌v�Z�ł��̒l���Z�o���邱�Ƃ�
�s�\�ł��邽��, ���k�v���O������p���Ēl���ߎ��I
�ɋ��߂邱�ƂɂȂ�B$bz2(x) $�𕶎���$x$ ��bzip2�ň��k
�����Ƃ��̃t�@�C���T�C�Y�Ƃ���Ə�񋗗�$d(x; y)$ ��
�ȉ��̂悤�ɋߎ������B
\[d(x,y) \fallingdotseq \frac{bz2(xy) - bz2(x)}{bz2(y)} \]
�@�܂����k���@$C$ ���ȉ��𖞂����Ƃ�O(log n) �̌덷
�͈̔͂Ŗ��\�ł���Əؖ�����Ă���B\\
\begin{enumerate}
\item �C�ӂ̕�����x �ɑ΂���$C(xx)=C(x)$ �ł���A�󕶎���ɂɑ΂��āA$C(��)=0$ �ł���B
\item �C�ӂ̕�����x; y �ɑ΂���$C(xy) �� C(x)$�B
\item �C�ӂ̕�����x; y �ɑ΂���$C(xy) �� C(yx)$�B
\item �C�ӂ̕�����x; y; z �ɑ΂���$C(xy)+C(z)��C(xz)+C(yz)$�B
\end{enumerate}

%�����܂Ł@���������

\section{�����̕�����}
%����̉ۑ�
�����̕������Ƃ́A��Ƀf�[�^���k�ɂ����Đ����𕄍���ɂ��邽�߂̎�@�ł���B �����̏ꍇ�͔C�ӂ́A���邢�͌��߂�ꂽ�͈͓��̐������Ȃ�ׂ��Z��������ŕ\�����A�S�̂̏��ʂ����Ȃ����邱�Ƃ��w���B �����̕������ɂ���ďo�͂���镄����͈�ӕ����\�ł���A�ӂ��ړ�����(prefix code)�ł���B��ӕ����\�ȕ����́A��ʂɌꓪ�����𖞂����B���̂��ߐړ��������ꓪ�����Ƃ��ĂԁB

\subsection{�A���t�@����}
�A���t�@�����Ƃ́A��i�@����(�P�i����, unary)�Ƃ��Ă΂��A���̐�����\���ϒ������̈�B �����Ȑ��ɂ͒Z����������A���΂ɑ傫�Ȑ��ɂ͒�������������蓖�Ă�B
�ϒ������̍ł��ȒP�Ȍ`�ł��邪�A�����ꂪ�����Ȃ肷���邱�Ƃ���A���t�@�����P�̂ŗp�����邱�Ƃ͏��Ȃ��B���ۂɂ͂��̉��p�ł���K���}������f���^�������p������B

\subsection{���C�X����}
�S���� (Golumb) ������ Solomon W. Golumb ���J�����������ł���B
���C�X (Rice) �����̓S���������̓��ʂȏꍇ�ŁARobert F. Rice ���̂��ɍĔ����������Ƃ���A�S�����E���C�X�����ƌĂ΂�Ă�B
�S���������̓p�����[�^$b$���g���Đ���$n$�𕄍�������B�A���S���Y���͎��̂悤�ɂȂ�B\\
  1. �� $p =n/b$, ��] $q =n\verb|%|b$ �����߂�B\\
   2.$p$���A���t�@�����ŕ���������B\\
   3. $b=2^k$�̏ꍇ$q$�� k �r�b�g���o�C�i������������B\\
   4. $b!=2^k$ �̏ꍇ�A$q$�� CBT �����ŕ���������B\\ 
3�̏ꍇ�����C�X�����ƌ����B���C�X�����̓p�����[�^$b$��ύX����ƕ�������ω�����B����̎����ł́A$b=8,16$�̏ꍇ�Ŏ������s���B




\section{�����f�[�^�E�����T�v}

\subsection*{�����f�[�^}
�����������낤�i�ďC�E���F��������q�i�������ꌤ��
�������j�j�Ƃ����\�t�g�ɓ��{�e�n�T�U�ӏ��̉����f�[
�^������B���̉����f�[�^���e�L�X�g���i�Ђ炪�ȁE�B
�̂ݎg�p�j�܂��u���v���u���v�A�u�ցv���u���v�A�u�́v��
�u��v�A�L�΂����͑O�̉��̕ꉹ�������������Ƃ���
���͂̏������������B


\subsection*{�O����1(pre1)}
50������1����Ή������ĕϊ�����B

\subsection*{�O����2(pre2)}
�g�p�p�x����������1����Ή������ĕϊ�����B

\subsection*{�O����1-r(pre1-r)}
�O����1���{�����f�[�^�Ƀ��C�X���������{���B\\
���C�X��������$b=8,16$�̂Q��ށB\\

\subsection*{�O����2-r(pre2-r)}
�O����2���{�����f�[�^�Ƀ��C�X���������{���B\\
���C�X��������$b=8,16$�̂Q��ށB\\

\subsection*{�����T�v}
���C�X�������ɂ��f�[�^���������Ȃ邩�m���߂邽�߁A�O����1,2���{�����f�[�^(��s����)�ƑO����1-r,2-r���{���f�[�^(�{����)�Ƃ̃t�@�C���T�C�Y���r����B\\
�����́A�ȉ��̂悤�ɍs���B

�����k(bzip2)�O\\
�O����1,2���{�����f�[�^�ƑO����1-r,2-r�̂��{�����f�[�^�Ƃ̃t�@�C���T�C�Y��r�B\\
���C�X������$b=8,16$�̂Q��ނōs���B\\

�����k(bzip2)��\\
�O����1,2���{�����f�[�^�ƑO����1-r,2-r���{�����f�[�^�Ƃ̃t�@�C���T�C�Y��r�B\\
���C�X������$b=8,16$�̂Q��ނōs���B\\



\section{�������ʁE�l�@}

�����k(bzip2)�O\\
\begin{center}
\includegraphics[width=6cm,height=6cm]{rice-8.eps}
\end{center}
�O����2-r���{�����f�[�^�̃t�@�C���T�C�Y���啝�ɏ������Ȃ��Ă���B\\

\begin{center}
\includegraphics[width=6cm,height=6cm]{rice-16.eps}
\end{center}
�O����1-r,2-r���{�����f�[�^���Ƀt�@�C���T�C�Y���啝�ɏ������Ȃ��Ă���B\\

�����k(bzip2)��\\
\begin{center}
\includegraphics[width=6cm,height=6cm]{bzip2-rice-8.eps}
\end{center}
�O����1-r���{�����f�[�^�̃t�@�C���T�C�Y���啝�ɑ傫���Ȃ��Ă���B\\

\begin{center}
\includegraphics[width=6cm,height=6cm]{bzip2-rice-16.eps}
\end{center}
�O����1-r���{�����f�[�^�̃t�@�C���T�C�Y���啝�ɑ傫���Ȃ��Ă���B\\


\section{����̉ۑ�}
���C�X�������������̕��ނɗL�����ǂ����͌����_�ł́A�킩��Ȃ������B����Abzip2�ȊO�̈��k���@�Ŕ�r�������s���A���������A���C�X�������������̕��ނɗL�����������s���B\\


\end{multicols}%2�i���̕��͂̏I���

\begin{thebibliography}{3}%�Q�l����({3}�F3�Q�l����������Ƃ����Ӗ�)
\bibitem{a}
Ming Li and Paul M.B.Vitanyi, �n�ӎ��|��KolmogorovComplexity and its Applications.\\
�R���s���[�^��b���_�n���h�u�b�N(1994)
\bibitem{b}
�x�� �K�i, Kolmogorov�L�q�ʂɊ�Â��ގ��x��p���������̎������ށ@(2007)

\bibitem{c}
S. W. Golomb, Run-length encodings, IEEE Transactions on Information Theory IT-12(3), 399--401.

Robert F. Rice, Some Practical Universal Noiseless Coding Techniques, JPL Publication 79-22, 1979. 

\end{thebibliography}%�Q�l�����I���

\end{document}%�h�L�������g�̏I���

