トライ構造を用いた共起情報の効率的記憶検索法に関する研究

様 式

6

三百子間ふ

文

目

3

_表

(

中

工)

報告番号

l

乙

工

第

₁₆₅

氏名

森 旧 和 宏

工

I

{

多

学位論文題目

トラ

イ

構造を用いた共起情報の効率的記憶検索法に関する研究

論文の目次 第1jき 緒 論 第2章 共起情報と辞書構成法 第3章 トライ情造 第41主 ダブル配列法 第5章 リンクトライ 第6章 評価と考察 第7車 結 論 参考論文 主論文 1.“トライ憐j査を用いた共起情報の効率的検索アルゴ'}ズムペ森田和宏，望月久稔， 111川善弘，青江順一，情報処理学会論文

誌

，

VoI..J9

，

No.9

，

pp.2563-2571 (1998)

2. "A Link Trie Structurc of Storing Multiple Attribute Rclalionshipsfor Nalural Languagc Oictionarics"， J(azllhiro Morita， l¥1asafumi Koyama， Masao Fukctan.nd Jun-ichiAoe， Jnterna.tional JOllrnal of Complllcr Mathematics， 1勺1.72，No.4， pp.463-176 (1999).

3."Fast Insertion Mcthods of a Doublc-Array Structure"， I{azuhiro Morita， Toru Sumitomo， Ma.sao Fukct.rI.and .Jun-ichi Aoe， Software Prλcticc & 8xpericncc.(条件付採録)

副論文

l“拡張ノ、yシユt法去における部分文字列倹索の設計と実現 誌， ¥101.38， No.2， pp.310-320 (HHJ7)

2.“特徴べクトルによる全文検完紫:の一改吉普子訂j法去 pp.826-829 (1998)

3.“.AP日tand Compact Data StructUI巴ofStoring Multi-Attribut.c Rclations among Words"， 1くaZllhiroMorita， ToruSumitomo， Masao Fukela and Jun-ichi Aoe， 1998 IEGE Internalional Confcrcncc on Systcms， Man， and Cybernetics， pp.2791-2796， San Dicgo， California， USA (Ocし1998)

4."A FastR.巴tricvingAIgorithm of [[icrarchical Rclationships Using Tric Struclurcs"

，

Masafumi Koyama

，

Kazuhiro I[orita， ，¥][asao Fllketa anclJun-ichiAoc， Information Proccssing & Managcment， Vo.134， No.6， pp.761-773

(1998)

5.“A Mcthod of Stori口gMulti-八ttribut.eRelations inNatural Langllagc Dictionaries"， Kazllhiro Morita， Makolo Okada

，

M出 aoFlllくe.taancl Jun-ichiAoe

，

Proc. of the 18th Int'1 Conf.on Comput巴rProccssil1g of Oricntal Languages， pp.437-442， Tok川lima，Japan (Mar. 1999)

6.“EfficientControlling of Parsing-Stack Operations for LR Parscrs"， Masao Fukcta， Kazuhiro Morita， Sangkon Lc巴andJun-ichi Aoe， 1川ernatio日 1Journal of lnformation Scicnccs， Vol.118， pp.I-15-157 (1999)

7. "Similarity m巴aSllresusing ncgativcwcight and its application Lo word日imilrl.rily"

，

EL Sλycd Atlみm，Kazuhiro Morita

，

l¥1'asao Fuketa and Jun-ichi Aoc

，

lnformation Proccssing & lVlanagcmcnt (印刷l中).

8. “複合詩の分野i連l~恕U巳.詩の 3労効1拘'}~率容的『決た定 i法去

9.“キーワードの遅延納山を考慮した文書検索構造の効率的構成法'¥阿国立，安!'I長一秋，森印刷15配，青江順一，情報処理学会 論文誌(粂件付採録)

備 考

l

論文目録は

，

用話が英語以外の外国語のときは日本記訳をつけて，外国間

，

日本誌の )

I

I

Nに列記するこ

と.

2

参考論文は

，

論文題目

，

著者名

，

公刊の )

J

法及び時期を

)

l

l

f

t

に明記すること

.

3

参考論文は

，

博上論文の場合に記載すること.

株式

7

論 文 内 容 要 旨

征二i)

報 告 番 号 ￨ 乙 工 第

165

号￨

氏名

森 田 和 宏

工 修

学位論文題目

ト ラ イ 構 造 を 用 い た 共 起 情 報 の 効 率 的 記 憶 検 索 法 に 関 す る 研 究

本論文は，自然言語昨書に間築される基本語棄の関係を定義することで無限に作り出され

る共起情報の効率的な記憶検索校法に関する研究の成果をまとめたものであり，以下の 7章

により構成される.

第

l

章では，緒論として

，自然、

言語処理システムにおける共起情報の利

用の歴史的背

景

を述べると共に，本研究の目的ならびにその工学上の意義を述べることで

，

本研究の意義及

び位置付けを明確にする

.

第 2章では，共起情報の概要と意義について説明する.また，自然言語処理システムにお

ける辞書の意義についても述べ，辞書:を構成する基木的なア

j

レゴリズムについて説明する.

第

3章では，辞書の構成法として最も適しているトライ構造について概要を述べ，その

検索，更新アルゴリズムについて説明する.

第

4

章では，

ト

ライ構造を実装するためのデータ構造について説明し，最も効率的な手

法であるダブル配列法について，検索，更新アルゴリズムとともに詳細に述べる.また，ダ

ブル配列法の問題点であるキー追加の速度を改善する手法として，ダブル配列で構築された

辞書を変更することなく高速化する手法と，ダブル配列に格納した情報を利用して高速化を

実現する手法を提案する

.

第

5

章では，共起￨育報を効率的に記憶検索する手法として，関連日f

宛とともに提案手法

であるリンクトライについて述べ，リンクトライにおいて定義されるリンク情報により，冗

長性を排除した効率的な記憶が可能となることを示し，同時に提案した梢造における共起情

報の検索，更新アルゴリズムを説明する.また，ダブル配列を用いたリンクトライのデータ

構造についても説明し

リンクトライのデータ構造を提

案する上で考案された

，複数の辞

書

を lつのダブル配列で管理する手法も述べる.

第

6

章では，提案手法に対して検索速度，記憶効率の理論的評価，及び実験による評価

を与え，本手法の有効性を確かめ，考察を加える.

第

7章では，本研究で得られた諸成果の総括を行い，今後の研究課題について述べる

.

トライ構造を用いた共起情報の効率的

記憶検索法に関する研究

2000

年

3

月

森 田 和 宏

， 内

"

'

"

トライ構造を用いた共起情報の効

率

的

記憶検索法に関する研究

2

0

0

0

年

3

月

森田和宏

内容梗概

本論文は，自然

言

語 辞

書

に構築される基本語棄の関係を定義することで無限に作り出

される共起情報の効率的な記憶検索伎法に関する研究の成果をまとめたものであり，以下

の

7

章により構成される

.

第 l章では，緒論として，自然

言

語処理システムにおける共起情報の利用の歴史的背

景を述べると共に，本研究の目的ならびにその工学上の意義を述べることで，本研究の意

義及び位置付けを明確にする

.

第 2章では，共起情報の概要と意義について説明する.また，自然

言

語処理システム

における辞書の意義についても述べ，辞書を構成する基本的なアルゴリズムについて説明

する

.

第

3

章では，辞書の構成法として最も適しているトライ構造について概要を述べ，そ

の検索

，

更新アルゴリズムについて説明する

.

第 4章では，

トライ構造を実装するためのデータ構造について説明し，最も効率的な

手法であるダブル配列法について

，

検索，更新アルゴリズムとともに詳細に述べる

.

ま

た

，

ダブル配列法の問題点であるキー追加の速度を改善する手法として

，

ダブル配列で構

築された辞書を変更する

こ

となく高速化する手法と，ダブル配列に格納した情報を利用し

て高速

化

を実現する手法を提案

す

る

.

第 5章では

，

共起情報を効率的に記憶検索する手法として，関連研究とともに提案手法

である

リ

ンク

ト

ライについて述べ

，

リンク

ト

ライに

お

いて定義されるリンク情報により

，

冗長性を排除した効率的な記憶が可能となることを示し

，

同時に提案した構造における

共起情報の検索，更新アルゴ

リ

ズムを説明する

.

また

，

ダブル配列を用いたリンクトライ

の デ

ー

タ構造についても説明し，

リンクトライのデータ構造を提案する上で考案された，

複数の辞書を

l

つのダブル配列で管理する手法も述べる

.

第

6

章では

，

提案手法に対して検索速度，記憶効率の理論的評価

及び実験による評

価を与え，本手法の有効性を確かめ，考察を加える

.

第 7章では，本研究で得られた諸成果の総括を行い，今後の研究課題について述べる

.

関連発表論文

{

主論文]

1

.森田和宏.望月久稔:山川善弘

1

青 江 順 一 :

“

ト

ライ構造を用いた共起情報の効ギ的検

索アルゴリズム

2

.

Ka

臼

z

u

h

i

r

、刀

'

0

:

t

¥

I

o

r

i

.

'

i

、凶

t

a

，

:

'

d

a

絹

s

a

f

白

umiK

く

O句

yama.

~Ia泊sao

Fuk

c

t

a

a

nd J

ム

u

川

n

ト-1

児

c

川

h

iA

oe:

.

.

_

-

¥

.

Link

T

r

i

S

t

r

u

c

t

u

r

e

o

f

S

t

o

r

i

n

g

¥

l

I

u

l

t

i

p

l

e

At

t

r

i

b

u

t

e

R

e

l

a

t

i

o

n

s

h

i

p

s

f

o

r

~atur

a

l

Language

Di

c

t

i

o

-n

a

r

i

e

s

"

，

I

n

t

e

r

n

a

t

i

o

n

a

l

J

o

u

r

n

a

l

o

f

Compllter

:

t

¥

I

a

t

h

e

m

a

t

i

c

s

，

¥

'

0

.

1

7

2

、

N

o

.

.

J

，

pp

.

-

16

3

-

i

-

!

G

(

1

9

9

9

)

3

.

Kazuhiro

1

I

o

r

i

t

a

‘To

r

u

Sumitomo

，

:

t

¥

I

a

s

a

o

Fuk

e

t

a

and

J

u

n

-

i

c

h

i

Ao

e

:

“

F

a

s

t

I

n

s

e

r

t

i

o

n

I

e

t

h

o

d

s

o

f

a

Double-Arra

y

S

t

r

u

c

t

u

r

e

"

，

S

o

f

t

w

a

r

e

P

r

a

c

t

i

c

e

&

Exp

e

r

i

e

n

c

e

，

(条件付採

録)

{

副論文

]

1.望月久稔

7

森 田 和 宏

7

獅々堀正幹?青江

}

I

I

真

一

:

“

拡張ハ

ッシュ法における部分文字列検

索 の 設計

と実現

1

¥

情報処理学会論文誌ぅ

Vo

1

.

3

8

，

No.2

，

pp

.

310

-

3

2

0

(

1

9

9

7

)

.

2

有田健，森田和宏

1

溝

1

-

f

IJ

昭二

7

青 江順

一 " 特徴 ベ ク ト ル に よ る 全 文 検 索 の

一改善法、

7

情報処理学会論文誌，

Vo

1

.

3

9

，

No

.

3

，

pp.826

-

829

(

1

9

9

8

)

.

3

.

Kazuhiro Morita

，

Toru Sumitomo

，

r.

v

I

a

s

a

o

Fuk

e

t

a

and

J

u

n

-

i

c

h

i

Aoe

μ

A F

a

s

t

and

Compact

Data

S

t

r

u

c

t

u

r

e

o

f

S

t

o

r

i

n

g

M

u

l

t

i

-

A

t

t

r

i

b

u

t

e

Re

l

a

t

i

o

n

s

among Words

"

，

1

9

9

8

IEEE I

n

t

e

r

n

a

t

i

o

n

a

l

Co

n

f

e

r

e

nce

o

n

System

s

，

¥

I

I

an

，

and C

y

b

e

r

n

e

t

i

c

s

，

p

p

.

2

7

9

1

-

2796

，

San

Di

e

g

o

，

Ca

l

i

f

o

r

n

i

a

，

USA (

O

c

t

.

1998

)

4

.

'

l

v

l

a

s

a

f

u

m

i

Koyama

，

Kazuhiro

~Iorita ，

~Iasao

Fuketa and

J

u

n

-

i

c

h

i

Ao

e

:

“A

F

a

s

t

R

e

-t

r

i

e

v

i

n

g

Algorithm

o

f

H

i

e

r

a

r

c

h

i

c

a

l

R

e

l

a

t

i

o

n

s

h

i

p

s

U

s

i

n

g

T

r

i

e

S

t

r

u

c

t

u

r

e

s

"

，

Inform

a

t

i

o

n

P

r

o

c

e

s

s

i

n

g

&

i

v

I

a

n

a

geme

n

t

】

Vo

.

1

3

4

，

1

¥

0

.

6

，

p

p

.

7

6

1

-773 (

1

9

9

8

)

lV

ο

.

I~azllhiro ~Iorita. ~Iakotü

O

k

a

d

a

.

~Iasao

Fuk

c

t

a

a

l

l

d

J

l

l

n

-

i

c

h

i

.-¥00

λ

¥

I

I

c

t

h

o

d

o

f

S

t

o

r

i

n

g

:

¥

h

d

t

i

-

A

t

t

r

i

b

n

t

e

.

R

e

l

a

t

i

o

n

s

i

n

:

¥

a

t

u

r

a

l

L

a

l

l

g

u

a

g

c

Di

c

t

i

o

n

a

r

i

e

s

司

Pro

c

.

o

f

t

h

c

1

8

t

h

I

n

t

I

Co

n

.

f

o

n

Co

m

J)

u

t

e

r

Pr

o

c

e

s

s

i

n

g

o

f

O

r

i

p

l

l

t

a

l

Lan

g

ua

g

e

s

，

p

p

.-

1

3i

-

-

l

-

l

2

T

o

ku

s

him

a

.

J

a

p

a

n

(

:

¥

I

a

r

.

1

9

9

9

)

6

.

:

¥

I

a

s

a

o

Fuk

e

t

a

;

E

a

z

u

h

i

r

o

¥

i

I

o

r

i

t

a

.

S

a

n

g

ko

Il

L

e

e

and J

l

l

l

l

-

i

c

h

i

λ

o

e

:

"E

斤

i

c

i

e

n

t

C

o

n

t

r

o

l

-l

i

n

g

o

f

P

a

r

s

i

n

g

-

S

t

a

c

k

Op

c

r

a

t

i

o

l

f

l

o

r

LR

Par

s

e

r

s

'

)

，

I

l

l

t

e

r

n

a

t

i

o

n

a

l

J

o

u

f

n

a

l

o

f

I

n

f

o

r

m

a

t

i

o

n

S

c

i

e

n

c

e

s

、

¥

'

0

1

.

1

1

8

、

pp

.

1

-

l

5

-

15i

(

1999

)

7

.

EL Sa

y

e

d A

t

l

a

m，

¥

l

I

a

s

a

o

Fukcta

，

Kazuhiro

¥

I

I

o

r

i

t

a

and J

u

n

-

i

c

h

i

Aoe

"

Simi

l

a

r

i

t

y

i

¥

I

e

a

s

l

l

r

e

l

l

l

c

n

t

Us

i

n

g

Term Ne

g

a

t

i

v

e

¥

V

e

i

g

h

t

and

I

t

s

A

p

p

l

i

c

a

t

i

o

n

t

o

i

Nord Sim

i

l

a

r

i

t

y

"

，

I

n

f

o

r

m

a

t

i

o

n

Pro

c

e

s

s

i

n

g

&

l

¥

Ianagement

】

Vo

.

1

3

6

，

N

0

.

3

(

2

0

0

0

)

(印刷中)

8

.

辻孝子?説、

田正

雄

3

森 田 和

宏?青江

1

)

1

買 ー "

複

合 語

の分野連想

詰

の効

率

的 決 定 法

3

¥

自然

言 語

処

理

1

Vo

1

.

7

，

NO.2 (

2

0

0

0

)

(

印刷中)

9

.岡田

真?安

藤 一

秋

1

森

田和

宏?青江 順-

•

"キーワードの遅延抽出を考慮した文書検

索

構

造

の効率

的 構 成 法ぺ

情報処理学会論文誌(条件付採録)

•

【

講演報告

}

1.森田和宏?望

月 久 稔

3

獅 々 堀 正 幹

?

青 江 順一 "

トライ構造を用いた共起情報の効率的

検索アルゴリズム

目

ノ

、

ん

人

7

内

容 梗概 .

関 連 発表

論 文

第

1

章 緒 論

第

2

章

共 起 情 報 と 辞 書 構 成 法

2

.

1

緒

言

- ・ ・ ・ ・ ・ .

2

.

2

共 起 情 報 .

・ .

2

.

3

辞 書 構 成 法

- ・ 4 ・ . . .

.

.

- ・ ・

2

.

4

結

言

.

.

.

.

第

3

章

トライ構造

3

.

1

緒

言

-ー ・ 4‘ ・

3

.

2

ト ラ イ 構 造 の 概 要 .

•

3

.

3

トライの圧縮

- ・ ・ a ・ a

3

.

4

結 言

- ー ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・

第

4

章

ダフ

j

レ配ヲIj法

4

.

1

緒 言

- ・ ・ ・ ・ ・ ・ . . . . - ー ・

4

.

2

トライのデータ構造

ー ・ ・ ・ ー - ・ ・

4

.

3

ダブル配列の検索アルゴリズム

4

.

4

ダブル配列の更新アルゴリズム

4

.

5

追 加 の 高 速 化

4

.

6

結 言

第

5

章

リンクトライ

5

.

1

緒

言

- ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ . - ・ 4‘ ・

5

.

2

共 起 情 報 の 格 納 構造

.

. ・ 111

1

3

3

3

: .:>

8

9

9

9

1

3

2

1

23

23

23

32

3-

1

45

54

55

55

55

V

5

.

3

リ ン ク ト ラ イ の 検 索 ア ル ゴ リ ズ ム

5

.

-

1

リ ン ク ト ラ イ の 更 新 ア ル ゴ リ ズ ム

5

.

5

リ ン ク ト ラ イ の デ ー タ 情 造 .

5

9

6

2

6

-

1

(O

7

9

7

9

7

9

8

2

87

8

9

9

1

93

95

99

101

図 目 次

5

.

6

結 言

第

6

章 評 価 と 考 察

₂

_.

₁

_{表 形 式 の 辞 書}

_{モ デ ル}

G

6

.

1

緒 言

₂

_.

₂

_{ハ ッ シ ュ 法}

6

.

2

理 論 的 評 価

6

.

3

実 験 に よ る 評 価

6

.

4

リンクトライの応用

3

.

1

キ ー 集

合

!

¥

'

1

に 対 す る ト ラ イ

3

.

2

遷移

g

(

s

，

α

)

=

t

.

.

.

.

3

.

3

i

η

d

e

g

r

e

e

(

s

)

=

2

，

o

u

t

d

e

g

r

e

e

(

s

)

二

3

の 例

3

.

4

キ

ー

集 合

!

{

2

に 対 す る ト ラ イ

3

.

5

シ ン グ ル ス ト リ ン グ を 用 い た キ ー 集 合

!

{

2

に 対 す る ト ラ イ

3

.

6

図

3

.

5

の ト ラ イ に ， キ -

"

b

a

b

y

l

on#

刊

を 追 加 し た 例

3

.

7

図

3

.

5

の ト ラ イ か ら ， キ -

"

badge#

日を削除した例

ハ

U

1

2

4

に

U

Q

U

O

-ム 1_l ム 1 ム 1_l ム 1 i 1 1 4 円 /

-6

.

5

結 言

第

7

章 結 論

謝辞

参 考

文

献

付 録

B

リ ン ク ト ラ イ の 実 験 に 使 用 し た キ ー 集 合

B

.

1

関 係 情 報 の 内 部 表 現 値

B

.

2

日 本 語 共 起 辞 書

•

.

1

0

1

4

.

1

配 列 を 用 い た ト ラ イ の 例

.

4

.

2

配 列 を 用 い た キ ー 集 合

!

{2

に 対 す る ト ラ イ

4

.

3

J

o

h

n

s

o

n

の 方 法

4

.

4

ダ ブ ル 配 列 構 造

- ・ ・ ・ ・ ・

4

.

5

K2

に 対 す る ト ラ イ と ダ ブ ル 配 列

.

.

4

.

6

ダ ブ ル 配 列 を ノ ー ド で 分 解 し た

例

- ・ ・ ・ ・ ・ ・ ・ ・

4

.

7

関 数

MO

DI

FY

の 動 作 例

2

-

1

付 録

A

ダ ブ ル 配 列 の 実 験 に 使 用 し た キ ー 集 合

₂

₅

4

.

8

図

4

.

5の ダ ブ ル 配 列 に キ ー “

bbq#"

を 追 加 し た 例

4

.

9

図

4

.

5

の ダ ブ ル 配 列 か ら キ ー

“

b

c

s

子学"を削除した例

4

.

1

0

S

k

i

P

_

T

α

t

e

の 値 に よ る 追 加 時 間 と 空 ノ ー ド の 割 合 .

4

.

1

1

範 囲 限 定 法 を 用 い た ト ラ イ と ダ ブ ル 配 列

4

.

1

2

関

委

文

SET

_EMPTY

_

L

INK

の重力作

4

.

1

3

空 ノ ー ド リ ン ク 法 を 用 い た ダ ブ ル 配 列

円 O Q u n U 1 i Q U 7 -A 吐 円 。 司 i

つ

ω A 吐

2

2

3

3

3

4

4

4

4

5

5

B

.

3

英 語 共 起 辞 書

.

1

0

3

.

1

0

6

5

.

1

!

{

3

に 対 す る ダ ブ ル ト ラ イ

5

.

2

C1

に 対 す る リ ン ク ト ラ イ の ト ラ イ 部

57

5

9

VI V11

5

.

3

図

5

.

) に 付 す る ダ フ ル 配 列 .

5

.

-

1

ダブル配ダiJ

D

(

f

(

1

7

)

)

の例

0.0

ダブル配列

DF

[

]

r

と表

hEYID

の例

5

.

6

トライ部とリンク関数の連結

5

.

7

C1

に 対 す る リ ン ク ト ラ イ の ダ ブ ル 配 列 表 現

5

.

8

C1

に 対 す る リ ン ク ト ラ イ の ト ラ イ 表 現 .

6

5

6

6

6

9

表 目 次

7

0

7

6

5

.

1

C1

に 対 す る リ ン ク ト ラ イ の リ ン ク 関 数

.

₆

₀

( (

6

.

1

キ ー 追 加 時 の 空 ノ ー ド の 割 合 の 結 果

6

.

2

提 案 手 法 で の 空 ノ ー ド の 割 合 の 結 果

6

.

3

ダブル配列のキー追加時間の結果

6

.

4

ダブル配列のキー削除時間の結果

6

.

5

記 憶 量 に 対 す る 結 果

6

.

1

リンクトライの実験結果

₈

_i

勺 J l t F h U ρ O Q u n x U 口 δ n δ n 6 n 6 Vlll IX

喧喧冒喧喧喧軍国国璽哩堕聞里国軍曹璽里璽雪璽喧喧喧国軍国国璽園園園国国璽璽園璽璽聞置

第

1

章

緒

=と〉

日間

自然言語処理システムにおける単語の共起情報は有用であり

，

自然

言

語解析における暖

昧性の解決手段

[

1

，

2

]，機械翻訳での訳語の選択

[

3

，

4

]，かな漢字変換の同音異義語の決定

[

5

，

6

，

7

]，音

声

認識における候補文字の制約

[

8

]

などに利用されており

，

それぞれの応

用辞

書

だけでも膨大な共起情報が必要となる

.

特に

，

形態

素

解析の精度向上でも必要となる基

本単語

1

から造語される長単位語

(

複合語と呼ぶ

)

は

，

文書検索システムの索引語におけ

る重要語

，

機械翻訳の訳語解釈などのよ

う

に 正確な意味解釈をする上でも必要不可欠な

ものであり

，

その数は膨大なものとなる

.こ

の観点より

，

共起情報を格納する辞書の効率

的記憶検索は重要な課題であるといえる

.こ

の課題に関連する研究として，複合語の接頭

辞と接尾辞を圧縮して格納

す

る手法

[

9

]

が提案されているが

，こ

の手法は

一

般的な共起情

報の格納方式を提案した

もの

で

は

ない

.

以上の

よ

うに

，

自然言語処理システ

ム

には様々な共起情報による知識辞

書

が必要である

が

，こ

れらの知識辞書の検索の切り口

(

キ一

見出し語

)

は

やはり形態素表記である

.

即ち

，

抽象的な概念

化

が行われたとしても

，

人間が認知する上で概念名も形態

素

表記に

合

致する場合が多い

.

例えば

，

LL

タ ク シ -

"

や“パス

"

は

，

tt

乗り物"と概念化されるが

，

この

概念名も形態素表記となる

.

従

っ

て，共起情

報

を格納する知識辞

書

は

自然

言

語処理シス

テムの基本辞

書

である形態素辞

書

の見出し語と融

合

して構築するのが効率的である

.

更

に，異なる属

性

の共起情報による

全

ての知識辞

書

を形態

素

辞

書

の中

に

統

合

化して格納でき

れば，その利便性は非常に高いものとなる

.

1

文

章

を構

成する最小単位の単語

即ち形態素表記を示す.

1

第

l

章 結 論

本論文では，

_I--記のような知識昨占:と形態素

6

'

F

~i: の統合

化な

どに

必要な段々な十J

j

}

1

l

'1'

8

r

-

i

l

を格納できるよう拡張性を持たせた

，

効率的な共起情報の記'憶倹索下j

去を提案する

.

メ

ト

;

子

法では

，

形態素去記が格納されたトライ上の葉ノード間のリンク関数により共

J

包情報を

定

義するので

，

登録による記憶の増加は

このリン

ク情報のみとなる

.ま

た

，こ

のリンク情報

に絞数の関係情報を格納する方式を提案

すること

で

，

種々の

自然

、

言訴処理システ

ムへ

の応

用￨生を高める

.

以下，

2

章で共起情報の

概

要と意義につい

て説

明

する.また，自然

言語

処理システム

に

おける辞

書の意義につい

ても述べ，辞

害

を構成する基木的なアルゴリズムについて説明す

る-

3

章では

，

辞書の構成法として最も適しているトライ構造について概要を述べ

，

その

検索，更新アルゴリズムについて説明する

.

4

章

ではトライ構造を実装するためのデータ

構造について説明し，最も効率的な手法であるダブル配列法について，検索，更新アルゴ

リズムとともに

詳

細に述べる

.

また，ダブル配列法の問題点であるキー追加の速度を改

善

する手法を提案する

.

5

章では，共起情報を効率的に記憶検索する手法として，関連研究

とともに提案手法であるリンクトライについて述べ

，ダブル配列を用いたリンクトライ

の

データ構造についても説明する

.また，リンクト

ライのデータ構造を提案する上で考案さ

れた

，複数の辞

書を

1

つのダブル配列で管理する手法も述べる

.

6

章では

，

提案手法の理

論的評価と実験による評価を与え，考察を加える

.

7章では，本論文のまとめと今後の課

題について触れる

.

2

第

2章

共起情報と辞書構成法

2

.

1

緒言

近年の計算機の発展により，複雑で高度な処理を高速に計算させることが可能になって

きた.それに伴い，自然言語処理システムにおいても多くの言語知識を利用して，システ

ムの精度を向上させることが可能となってきている

.

その意味で，自然

言 語

処理システム

における共起情報の必要性はいっそう増してきており

，

共起情報を利用するさまざまな研

究がなされている

.

また，自然言語処理システムにおいて

，

辞書は必要不可欠なものであり，辞書の量と質

によってシステム全体の能力が左右されるため，システム構築の上で，最も労力を割かれ

るものでもある

.

本章では，自然言語処理の基礎となるこれらの共起情報と辞書について，概要を述べる

ことでこれらの意義を確認する

.

2

.

2

共起情報

自然言語処理システムにおける共起情報の有用性はきわめて高く，自然

言 語

における暖

昧性や多義性を解消し，システム全体の精度を向上させる上で非常に重要な情報であり，

共起情報を

利用するさまざまな研究

[

1

0

，

2

，

1

1

]

がなされている

.

ま た ， 元 来 人 手 に よ り 収 集 さ れ て き た 共 起 情 報 は ， 収 集 者 の 視 点 に よ り ば ら つ き が 見

3

第

2

卒

:

共起情報と辞書構成法

られたり，時間的制約による収集量の限界があったが，共起情報白イ

イ

ミの精度向上を日

J

旨し

一，大量のコーパスから客観的手法により抽出し，その結果を利用する研究

[

1

2

.

1

3

]

も多

くなされている

.

これらの共起情報は，通常

2

単語間に存在する意味的関係を定義し，本論文では基本単

語_

¥

，

1

-

間に関

係

情 報

α

が定義されるものとし

，

(

_

¥

，

1

-

.

α

)

で

表 す

.

この関係

情 報

α

は以

下の様々な形態での定義と検索要求がある

.

(

A

)

概 念 階

層の上位

と下位の関係

(階層関

係

)

シソーラスで代表される分

類

体系

(

概念￨者

層と

[

1

乎

ぶ

)

は，非常にシン

プル

な知識表現

であり，応用範囲は非常に広い.この表現の基本的推論は，概念“衣類"と

t

~カ y ター

シャツ‘:などの上位と下位の関係であり， ("カッターシャツヘ・

4

衣 類

n

，

上位語)なる

共起情報で定義

される

.

また，

(

.(アメリカペ

"

国

名

?

に 上 位 語 )，

(

"

カナダペ“

国名門

，

上位語)も定義できる

.

(

B

)

格構造における動詞と名詞句の関係(格関係)

格構造は，動詞に対する名詞句の意味的制約を倍納するものであり，例えば動詞“合

う

"

の

主

格名

詞

句には

，

概念“衣類

円

や表記“気候刊の制約があるので，格関係におい

て (

“

合

うヘ“衣類

37

，

主格)， (

“合

うぺ

“

気 候

33

，主格)

が

得られる

.

なお

，

格 関 係 (

"

合

う

?

?

，

u

カッターシャツ

n

，

主格)は

，

(u

カ

ツ

夕一シヤツ

n

ぺ

，

tμt

衣 類

?

"

1

¥

，

上位語)と('“

t

合

う

日

ヘ

，

“衣類

(

ρ

C

)

慣用句関係や選択宣言関係

"

i

由を売る

"

からの (

(

(

i

由

n

，

tt

売る??

，

慣用句)や

，

ぺ馬カが

f

九

し

い

E

ななくぐ"カか、らの

(γtμt

馬

な

く

?

円

3

¥

，選択宣

言

)

•

(

D

)

同音語判定関係

上記の

(

B

)

の例も格関係による同音語判定関係の共起情報を意味する

.

この他に

，

名

詞句の共起による同音語判定関係として

，

“シヤツの生地円でで、同音語

t

“

t

記 事

η

を区別す

る("衣類円ヘ，

じ;生地

t η

，同音詰判定)や“アメリカの気候円を

u

帰

j

巷牢】?と区別する("国名

3η3¥

_，

:

、

気

候

(

E

町)複合語関係

4

"

カナダ

国籍刊を造語

する

("同名??

，

tt

国

籍?¥複合語)や(

“

アメリカ

37

，

tt

合 衆 国

1 ¥

複

合語)

2

.

3

.

辞書構成法

(

F

)

日失対訳関係

(

同義語

)

(パソコン，

"

p

e

r

s

o

l

l

i:l

l

computer"

，対訳)

(

G

)

同義語関係

(アメ

リヵ，

日

合衆国

-

-

，同

義語)

，

(

・

・

カ

ッタ

ー¥・・

カッターシャツ

，

・

同義語の短縮話)

広 義 に 解 釈 す る と 共 起 情 報 は

，以

上 の 例 に と ど ま ら ず (

一

前略

，

早 々 ， 頭 語 結 語

)

(

"

.

サ

ッ

カーペパスポーツ、¥分野

分類)など非常に多く存在する.

以 後

，

簡 単 の た め 関 係 情 報

α

は記号

α1

，

G2.

. 等 で 表 す

.

2

.

3

辞書構成法

共起情報に限らず，自然言語処理システムにおいて言語知識は大変重要である.計算機

が

言 語

を解析したり生成したりすることができるようにするには，

言語知識を蓄え

，それ

を使えるようにしなければならない

.

自然言語処理では，言語に関する知識は，文法規則

集 や 辞 書 と し て ま と め ら れ

文の解析や生成をする際に参照される

.

このため，自然

言 語

処 理 シ ス テ ム で は

，

辞 書 に な い

言 葉 が

使われたり，辞書の情

報

が

誤 っ て い た り 矛 盾 し て い た り す る と

，

平 気 で 誤 っ た 解 釈 を 行 っ た り ， 判 断 を 停 止 し て し

まったりする

.

従って

，

言 語

知識を辞書システムから取り出してくることは

，

自然言語処理のあらゆる

段階で

必

要となる最も基本的な操作となり

，

辞書構成の量と質によって自然

言語

処理の能

力

は

大き

く

左右される

.

また，言語知識は，多種多様な分類の仕方があるので

，

分類ごとに辞

書

が作成され

，

自

然言語処理のシステムによって必要な辞書を複数選定し

，

使用している

.

共起情報をまと

めた共起辞書は

その重要性から現在では概ねどのシステムにおいても使用されている.

以上のことから

，

辞書構成法や辞書システムに関する多くの研究

[

1

4

，

1

5

]

がなされてい

るが，本節では

，

辞書システムを構成する基本的なアルゴリズムについて述べる

.

b

第

2

章

共 起 情 報 と 辞 書

情成

法

キ

-1

レコード

1

キ

-2

レコード

2

キ一刀

/

4

レコード刀

/

4

キ一刀

/

2

レコード刀

/

2

キ

-n

レコード

ρ

図

2

.

1

表形式の辞書モデル

2

.

3

.

1

2

分探索法

辞 書 シ ス テ ム に お け る 最 も 単 純 な モ デ ル は

図

2

.

1

に示すような表形式のモデルであ

る.すなわち，辞

書

の

1

項目が見出し諸に対応するキーと見出し語に関する情報に対応す

る内容

(

レコード

)

からなる

.共起辞書は

，

2

単語間の関係を調査する目的で使用される

ため，検索キーとして

X

，

Y

が与えられるが，これらを

一

意に決定するために，通常連鎖

詩 嚢

_

¥

1

'を構成し，この

XY

をキーとして辞書が構築される

.

このため，キー数が著し

く増加し，記憶

量

との兼ね合いから，頻繁に使用される共起情報のみを登録している場合

が多い.

このモデル

に

おいて

辞

書

検索はキーを指定したときにその内容を選び出す探索の問題

となる.

最も

単

純

な

探

索

法は線形深索法であるが

，この手法は表の先頭から

I

I

!

買

に入力キーと各要

素の

キーが一致

す

る

かを比

較し

ていくため，キー数が

η

の

とき

計

算

量

が

O

(

η

)

となり，実

6

2

.

3

辞 害

構

成 法

k

e

y

l

0

5

匠亙回

図

図

2

.

2

ハッシュ法

用規模の辞書のキー数数千

数十万に対しては現実的な手法ではない.

これに対して，表中のキーが順序関係に従って並べられている場合は

2

分探索法が利用

できる

.

2

分 探 索 法 で は ， ま ず 始 め に ， 表 の 中 央

η

/

2

の要素のキーと入

)

J

キーを比較し，

もし入力キーが

η/2

のキーより小さければ求めるキーは

η/2

より前の位置にあるので，次

に

n

/

4

のキーと比較する

.

このように，

1

回の比較を行うたびに探索範囲が半分になるの

で，計算量が

O

(

l

ogη)

となる.

2

.

3

.

2

ハッシュ法

ハッシュ法は代表的な表探索法であり

，キー

をハッシュ表に分散記憶し，ハッシュ関数

による香地計算によりキ

ーを

探索する手法である

(

図

2

.

2

)

.こ

のため，計算量は事実上

。

(

1

)

となる

.

ハッシュ法で、用いられるハッシュ表の各要素はパケ

ッ

ト

(

b

u

c

k

e

t

)

と呼ばれ，番地が付

けられている

.パケットの香地は，キ

-k

に対するハ

ッ

シュ関数

H

により

H

(

k

)

として計

算される

.即ち，ハ

ッ

シュ表の大きさを

1

1

1

とするとき，ハッシュ関数はキー集合を

O

か

ら

1

1

1-

1

の番地の集合に写像するキ一番地変換関数である

.

また，通常キー数に対して

f

の値は小さいので，異なるキーがハッシュ関数によ

っ

て同じ番地に写像されるという，

衝突が起こる.

第

2

章

共起

1'

・

1

5

践と辞書

情

成

i

L

ハ

y

シュ

j

去は

，

女

n

{

I

l

J

'

こ

衝

突を効ギ的

に

解消するかが重要な

問

題であるが

，

最

も簡単

なノ

j

法としては

，

チェイン法がある(凶

2

.

2

は

チェ

イ

ン法の例)

.

チェ

イ

ン訟

は，衝

突したキー

をポイ

ン

タで鎖の

よ

う

に

連結して十各市内

す

る方法で

，動

的

キー

集合への

適用

が可

能

で

あ

り

，

表が一

杯

になっても

，あ

ふ

れ

領域を

別

に

と

る

こ

とが

で

き

る.

2

.

3

.

3

トライ法

日

本

語

文

の

形態

素

解析を行う場

合に

は，入力

文

'!-，のどの部分が単

語

であるかというこ

と

がわか

っ

ていないため，入力文のある位

置

か

ら

末尾までの文字列の中で，その位置か

ら

始まる

全

ての

単語

を取り出す必要がある

.

このことを，表形式の辞

書

モデルで実現するに

は，まず

最

初

の

l

文字が単語であるか辞書引きし，次に

2

文字の文字列を辞

書

引きし，こ

れを

3

文字，

4

文字と繰り返し，最後に末尾までの文字列で辞書引きする必要があり，こ

の処理を入力文中の各位置で行うので，入力文の文字数を

J

とすれば辞

書

引きだけで

O(

L

)

の

計

算

量

が必要になり，非常に効率が悪い.

このように単

語

が雁定していない場合の辞

書

引きに適した探索アルゴリズムとしてトラ

イ法がある. トライについては次章以降で詳細に述べる.

2

.

4

結言

本章では，共起情報の概要と意義について説明した

.そし

て，自然、言語処理システムに

おける辞書の意義についても説明し，辞書を構成する基本的なアルゴリズ

ム

について

，2

分探索法，ハッシュ法について述べ，共起辞書の構成法とその問題点についても述べた

.

また，

トライ法について簡単に触れた

.

次章ではこのトライ構造について詳しく説明する

.

8

第 3

章

トライ構造

3

.

1

緒言

与えられた文字列がキーワードとして登録されているか否かを調べることは

計

算機処理

の基本であり，キー検索と呼ばれる

.

キー検索技法に対する要求は利用分野により異なる

が，近年の計算機の利用分野の拡大により様々なものが研究

・

実用化されている

.

なかでも，キーの表記文字単位に構成された木構造であるトライ構造は，登録キーの総

数に依存せず高速な検索ができること，検索失敗位置の特定が容易であること，検索文字

列中の接頭辞の検出が容易であることなどの理由により，形態素辞

書

，かな漢字変換辞

ョ

書

などの自然言語辞書を中心として広く用いられている

.

本章では，まずトライ構造の概要について述べ，大規模キー集合におけるトライの記憶

量軽減のための圧縮法について説明し，このトライに対するキーの検索，更新アルゴリズ

ムについて述べる.

3

.

2

トライ構造の概要

トライ(

t

r

i

e

)

構造は

ぺ

r

e

t

r

i

e

v

a

l

ll

の

真

中のス

ペ

ル

し

t

r

i

e

η

_{を語源とし}

_，

F

r

e

d

k

i

n

[

2

0

]

_により命

名された

.

発

音

上，木

(

t

r

e

e

)

と区別するためにトライと呼ばれる

.

2

分探索木や

B

木な

どの木を利用する探索アルゴリズムが

，

分岐する校を選ぶのにキー同士の比較を使うの

に対し，

トライは，キーの値

自

身による添字付け

に

よ

っ

て分岐する校を決定する

.

このた

9

第

3

章

トライ構造

@ら⑬三~

図

3

.

1

キー集合

f

ピl

に対するトライ

め

，

トライはキーを構成する文字を単位として木構造を構成し，探索も

一

文字ごとに行わ

れる

.

図

3

.

1にキー集合

K

l

={

t

t

babynfbachelor

1

¥

“

backγ'badge"

，

"

b

a

d

g

e

r

"

“

，

b

a

d

n

e

s

s

ぺ

"

b

c

s

"

}

に対するトライを示す.図中の

2

重丸で示されるノードは出力ノードである

.図

3

.

1に示

すように，

トライは，キーの共通接頭辞が併合圧縮される

.

また，

トライ上で深さ九の位

置にあるノードはキーの九番目の文字に依存し，その遷移先はキーの九十

1

番目の文字に

より決定される

.従って，検索時間は検索キーの長さに依存し，登録されているキーの総

数には依存しないので，大規模なキー集合を取り扱った場合でも，検索の高速性が損なわ

れることはない.

以後の議論のためにここでいくつかの定義を示す.

[定義

3

.

1

J

トライ上で，ノード

s

か

ら

ノード

t

への遷移が記号

αに対して定義されていれば，関数

gを用いて，

g

(

s

，

α

)

=

t

1

0

3

.

2

ト

ラ

イ構

造の

概

要

図

3

.

2

遷移

g

(

s

，

α

)

二

f

と書き(図

3

.

2

)

，そうでなければ，

g

(

s

，

α

)

=

1

α

i

l

と

書

く

.

この関数

g

は

g

o

t

o

関数と呼ばれる.また，連続する遷移の並び、

を

パス

(

p

a

t

h

)

と

呼び，

g

o

t

o

関数はパスに対しても利用され，パス上の記号による文字列

X

に対して，

g

(

s

，

.

X)

=

t

と記述する

.

(

定義終

)

[

定義

3

.

2

J

g

o

t

o

関数

g

に対する逆関数を

g

-

l

と定義し

，

g

(

s

，

α

)

=

t

に対して

，

g

-

l

(

t

，

α

)

=

s

と書く

.

(

定 義 終

)

[

定 義

3

.

3

J

ノー

ドs

に対

し

て

，

s

に入る遷移の数を，

1

1

第

3

章

トライ悦近

。

図

3

.

3

η

i

d

e

g

r

e

e

(

s

)

=

2

，

o

'LL

t

d

e

g

r

e

e

(

s

)

=

3

の例

1η

d

e

g

r

e

e

(

s

)

で表し，

s

から出る遷移の数を，

o

u

t

d

e

g

r

e

e

(

s

)

で表す(図

3

.

3

)

.

トライにおいては ，

i

n

d

e

g

同

e

(

s

)

は常に

l

となる

.

また ，

o

u

t

d

e

g

r

e

e

(

s

)

=

0

なるノード

s

を最終ノードと呼ぶが，

トライは木構造であるので，葉ノードと呼ぶ場合も

ある

.

(定義終)

[

例 3

.

1

J

図

3

.

1

の ト ラ イ 上 で キ -"

badger

"を検索

す る 場 合 を 考 え る . ま ず 最 初 に ノ ー ド

1

から

スタートし，

g

(

l

，

'

b

'

)

=

2

により，ノード

l

から文字

(

b

'

を辿りノード

2

へ到達できるので，

文 字

'

b

'

がマ

y

チしたことになる

.以

後同様に，

g

(

2

，

'

a

'

)

=

3

により，ノード

2

から

(

a

'

を辿

りノード

3

へ

，

g

(

3

，

'

d

'

)

二

1

3

，

g

(

1

3

'

，

ピ)

=

1

4

，

g

(

1

4

，

'

e

'

)

=

1

5

，

g

(

1

5

，

γ)

=

16

により，ノー

ド

1

6

に到達する.このノード

1

6

は，出力ノードであるので

，キ

ー

"badger"

の 検 索 に 成

功したことになる

.

(例終)

1

2

3

.

3

トライの圧縮

トライへのキーの追加，削除はキ-_yに対して

y

(

l._¥)二 t

(

t

は出力ノード

)

を定表

するか，削除することで簡単に行うことができる.

例

3

.

1

において，

g

(

l

--1

.

.

e

・

)

=

1

5

により，ノード

1

-

-

1

か

ら

1

5

へ の 遷 移 が 起 こ っ て い る が

こ

のノ

ード

1

5

は

出力ノ

ードであ

る

.

つまり

，キー

'

.

b

a

c

l

g

e

r

"

を検索する過程において，キ-"

b

a

c

l

g

c

"

を発見することが可能であり，このことは，任意の入力文字列に対して，キーの

最長

一

致 検 索 や 接 頭 辞 の み が 一 致 す る 検 索 を 容 易 に さ せ る

.

このためトライは，

語と語の間に空白を持たない白然言語(日本語

，

中国語など)での

形 態 素 解 析 に お い て ， 最 適 な 辞 書 引 き を 行 う ア ル ゴ リ ズ ム と さ れ て い る

[

2

1

]

，

3

.

3

トライの圧縮

前節でも述べたように，

トライは共通接頭辞を併合する特徴をもつが，

一度

ノ

f

スが分岐

すると以降は共通な接尾辞をもっキ一同士の間でも

J

妾尾辞の併合は行われず，各キーは他

のキーとは独立して接尾辞に対して遷移を作るため，接尾辞の記憶に関して記憶量の節約

は行われない

.

このため，大規模なキー集合を取り扱うと，

トライのノード数は膨大なものとなり

よ

り多くの記憶領域を必要とするという問題が生じる

.

そこで，

トライのノード数を縮小するために，シングルストリングを導入する

.

導入の

準 備 と し て

，キー

に 現 わ れ な い 端 記 号

(

e

ndmark

e

r

)

[

2

2

]

'

#

'

を

キーの最後尾に付加する

キ ー 集 合

K1

に 端 記 号 を 付 加 し た キ ー 集 合

K2

に 対 す る ト ラ イ を 図

3

.

4

に示す

.

図に示

されるように，端記号を用いたトライでは最終ノードと出力ノードが常に一致する.

以下に

，セ

パレートノ

ード，

シングルストリングの定義を示す

.

[

定 義

3

.

4

J

goto

関数に対して，次のノードを定義する

.

g

(

r，

α

)

=

t

，

o

u

t

d

e

g

r

e

e

(

ァ

)

三

2

なるノード

t

か ら 到 達 可 能 な 最 終 ノ ー ド ま で の 遷 移 列 上

に

，

o

u

t

d

e

g

r

e

e

(

k

)三

2

なるノード

k

が 存 在 し な い な ら ば ， ノ } ド

t

を セ パ レ ー ト ノ ー ド

(

s

e

p

a

r

a

t

e

node)

と呼ぶ

.

セ パ レ ー ト ノ ー ド は ， 検

索中のキ

ーを他のキーと

一意に区別

す

る 最 初 の ノ ー ド で あ り ， セ パ レ ー ト ノ ー ド 以 降 は 遷 移 の 分 岐 は 存 在 し な い

.

1

3