Search Engine in Debian

Asia Debian MiniConf 2005

NOKUBI Takatsugu

knok@debian.org

takatsugu.nokubi@toppan.co.jp

Agenda

Algorithms

Asian language issue

Packages in Debian

Improve Debian Documentation System

To the fearute

Algorithms

Inverted Index

N-gram

Suffix Array

Inverted Index

Search

Engine in

Debian ...

File-A

There is a

steam

engine ...

File-B

Debian

Socal

Contruct

File-C

search

engine

debian

File-A

File-A

File-A

File-C

File-C

File-B

Inverted Index

Pros:

Smaller than other method

Useful if query word is correctry

Cons:

Need to segment each words (in some languages)

Hard to match the part of word

Hard to match the phrase

Need to record each positions of words

N-gram

D

E

B

I

A

N

D

E

E

B

B

I

I

A

A

N

the word

the index (bi-gram)

N-gram

Pros:

Be able to match the part of any word

No search missing

Cons:

Too many match

Expensive calculation cost

Suffix Array

D

E

B

I

A

N

A

N

B

I

A

N

D

E

B

I

A

N

E

B

I

A

N

I

A

N

N

Array of pointers(sorted)

Suffix Array

Pros:

No search missing

Cons:

Huge index

4 times (on 32bit environment)

Need to remain the original source

Expensive on indexing (sorting)

Asian language issue

Word segmentation

word suffix(in Japanese)

Character encoding

Word segmentation

Japanese and some asian lauguage is written with no space between each words.

To make the inverted index, you need to split each words.

Debian

とは

何

か

Debianとは何か

("What is Debian?")

How to segment

Longest match from dictionary

KAKASI (for Japanese)

Morphological analysis

Noun, Verb, ...

ChaSen (for Japanese)

MeCab (for many languages)

but still have only Japanese dictionary

Word suffix

It is like stemming in English

move, moves, moved, moving, ...

動く

動

base style

か

ない

動

き

ます

動|か|せない

動|か|しよう|が|ない

動|か|なかった

more variants

Character encoding

A B C

D E F

... Y Z

Alphabet

A .. 0x41

B .. 0x42

:

Z .. 0x5A

ASCII

A mapping between a letter and an identify code

Many encodings

Chinese

GB2312 (EUC-CN)

Japanese

ISO-2022-JP

EUC-JP (Extended UNIX Code)

Shift JIS

There are some valiants

Korean

EUC-KR

How to handle their encodings

Need to convert into one encoding

Some encodings don't cover other encoding's character sets

Encoding detection

Can't do perfectly

Seems exactly same as EUC-CN/JP/KR

Unicode issue

Some letters in CJK were mapped into one code

Seach Engine in Debian

htdig

mnogosearch

swish++

sary

namazu

ht://Dig

Inveted index

Be able to handle local file

Famous software

since 1995

http://www.htdig.org/

mnoGoSearch

Inveted index

Be able to handle local file

Multiple backend support

PostgreSQL, MySQL, SQLite

Internationalization

CJK support

Japanese/Chinese word segmentation

http://search.mnogo.ru/

SWISH++

Inveted index

Be able to handle local file and remote document

HTML, mp3, LaTeX, e-mail, manpage, rtf

UTF-8 support

But no word segmentation

http://homepage.mac.com/pauljlucas/software/swish/

Sary

Suffix Array

Be able to handle one single local file

UTF-8/EUC-JP support

There are some bindings

Perl, Ruby

http://namazu.org/~satoru/sary/

Namazu

Inverted index

Be able to handle local file

Various format support

English/Japanese support

Stemming

Japanese word segmentation

http://www.namazu.org/

Estraier

Inverted index

Uni-gram or MeCab support

Be able to handle local file

Various format support

CJK support

http://estraier.sourceforge.net/

Not yet in Debian

ITPed by UKAI Fumitoshi

Improve Debian Documentation System

dwww

Online documentation system

Multiple file format support

HTML

Info

Manpages

Working with SWISH++

No i18n/m17n

dhelp

Another online documentation system

Aiming at /usr/share/doc

no manpages, infos, ...

but simple

Working with SWISH++

No i18n/m17n

What's wrong?

/usr/share/doc

There are no i18n policy

Hard to determine languages/encodings

Info

no i18n policy

manpages

better than the above

/usr/share/man/$LANG

So what is needed?

i18n policy

Language prefix

usually used for the content-negotiation on Apache

indexing/searching wrapper

There are many languages and hard to support all of it

To fit required language

SWISH++ for Latin languages users

Namazu for Japanese users

mnoGoSearch for Chinese users

To the feature

Desktop search system

like Google, Yahoo, ...

Web cache search

local cache (depend on browsers)

Squid

WWWOFFLE

Desktop Search

GNOME: Beagle

http://www.gnome.org/projects/beagle/

Based on DotLucene

Lucene is a search engine implemented by Java

Dot Lucene is implemented by Mono

KDE: not yet

will be implemented on KDE4

Requirements

Internationalization

Mutiple file format support

rich format

OpenOffice.org documents

HTML/XML

simple format

email, plain text

archive format

tar, zip

User-friendly frontend

Web cache search

There are some implementations

WWWOFFLE

ht://Dig, Namazu support

Integrated user-interface

Squid

Namazu supports squid cache format

Not there for local cache

Mozilla, Firefox, ...

Need to integrate with Desktop search

Conclusion

There are many implementations

and packaged in Debian

But still not useful

i18n/m17n issue

no integrated interface

We need i18n documentation policy

2005-02-10T08:23:51