사전을 만드는데 자료구조가 어떻게 될까요....

luftpalen의 이미지

어떻게 가장 빨리 데이터에 접근할 수 있을까요?

적게는 수십KB 많게는 몇메가나 하는것을 트리로 쓰자니 너무 오버헤드가 큰것같아서요..

해싱을 생각중인데 단어의 첫글자 알파벳으로 해싱테이블을 만든다 치면 그 다음 단어는 어찌접근해야 할까요... 첫 알파벳을 해싱테이블로 구현하고 링크드리스트나 트리를 쓰려니 azzzzzz 같은 단어가 최악의 상황이 될것같고..

사전 만들어보신분의 조언이나 관련 사이트 부탁드립니다..
좋은 하루 되세요

제리의 이미지

해싱의 경우, 키를 포인터로 잡으시고 단어길이 체크하신후에
그 키를 증가시켜가면서 사전의 단어와 비교하시면 됩니다.

이번학기 자료구조 수업 과제였었습니다...^^

수고하세요~~

가늠할 수 없는 사랑...

marten의 이미지

trie를 쓰지 않나요? trie를 구글링하시면 될 듯...

litdream의 이미지

luftpalen wrote:
어떻게 가장 빨리 데이터에 접근할 수 있을까요?

적게는 수십KB 많게는 몇메가나 하는것을 트리로 쓰자니 너무 오버헤드가 큰것같아서요..

해싱을 생각중인데 단어의 첫글자 알파벳으로 해싱테이블을 만든다 치면 그 다음 단어는 어찌접근해야 할까요... 첫 알파벳을 해싱테이블로 구현하고 링크드리스트나 트리를 쓰려니 azzzzzz 같은 단어가 최악의 상황이 될것같고..

사전 만들어보신분의 조언이나 관련 사이트 부탁드립니다..
좋은 하루 되세요

사전은 아니지만, Data Dictionary 를 b+ tree 로 만들어 본적은 있습니다.
고급자료구조 수업의 프로젝트였습니다.
insert 까지는 괜찮습니다만, delete 하면 쉽지 않습니다.

삽질의 대마왕...

saxboy의 이미지

Quote:
insert 까지는 괜찮습니다만, delete 하면 쉽지 않습니다.

보통 사전은 rdonly인 경우가 많아서 아예 delete를 구현하지 않기도 하지요. ;-)

vacancy의 이미지

trie가 가장 무난하지 않나 싶네요.

peccavi의 이미지

잡담입니다만, 예전에 한번 비슷한 테스트를 해야할 일이 있어서 고민한적이 있습니다.

임의의 단어 샘플을 가진 텍스트 파일을 다음과 같이 만들었습니다.

aaaaaaaaaa
aaaaaaaaab
aaaaaaaaac

...

zzzzzzzzzx
zzzzzzzzzy
zzzzzzzzzz

이 파일을 읽어서 입력된 문자열을 최단시간에 찾는 테스트였는데,

처음엔 해시테이블을 구현할까 생각하다가, 호기심에 무식하게 한번 해봤더니

속도가 생각보다 무지 빠르게 나왔었죠..

if( strncmp("zzzzzzzzzz", pSample, 10) == 0 ) return true

어찌 보면, 단순한게 좋을수도 있을것 같네요 :)

----
jai guru deva om...

atie의 이미지

자바여서 도움이 될지 모르겠지만, 예제를 볼 수 있으니 참고해 보세요.
http://java.sun.com/developer/JDCTechTips/2002/tt0709.html

----
I paint objects as I think them, not as I see them.
atie's minipage

정태영의 이미지

luftpalen wrote:
어떻게 가장 빨리 데이터에 접근할 수 있을까요?

적게는 수십KB 많게는 몇메가나 하는것을 트리로 쓰자니 너무 오버헤드가 큰것같아서요..

해싱을 생각중인데 단어의 첫글자 알파벳으로 해싱테이블을 만든다 치면 그 다음 단어는 어찌접근해야 할까요... 첫 알파벳을 해싱테이블로 구현하고 링크드리스트나 트리를 쓰려니 azzzzzz 같은 단어가 최악의 상황이 될것같고..

사전 만들어보신분의 조언이나 관련 사이트 부탁드립니다..
좋은 하루 되세요

어짜피 처음 로딩될 때... 메모리에.. 단어들은.. 로딩할테니..
바이너리 search 로 하는 방법도 있습니다..
...

검색이 잦아질수록.. 트리가 유리하겠군요 ..
요새 메모리야 워낙 고용량이니 =3=33

오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...

http://mytears.org ~(~_~)~
나 한줄기 바람처럼..

charsyam의 이미지

luftpalen wrote:
어떻게 가장 빨리 데이터에 접근할 수 있을까요?

적게는 수십KB 많게는 몇메가나 하는것을 트리로 쓰자니 너무 오버헤드가 큰것같아서요..

해싱을 생각중인데 단어의 첫글자 알파벳으로 해싱테이블을 만든다 치면 그 다음 단어는 어찌접근해야 할까요... 첫 알파벳을 해싱테이블로 구현하고 링크드리스트나 트리를 쓰려니 azzzzzz 같은 단어가 최악의 상황이 될것같고..

사전 만들어보신분의 조언이나 관련 사이트 부탁드립니다..
좋은 하루 되세요

Perfect Hashing 도 괜찮을듯 하네요 ^^

=========================
CharSyam ^^ --- 고운 하루
=========================

익명 사용자의 이미지

trie

익명 사용자의 이미지

자랩, ZaLab을 이용해 보세요
http://lab.zagia.com

좋은 정보가 있을 겁니다

simpid의 이미지

자료구조에 고수가 아니라.. 어떤걸 써야 할지는 모르겠지만..

사전 프로그램은 화면 한쪽 구석에 항상 실행되고 있을 수 있다는 조건은 갖아야 할듯 합니다.

그러므로 단어 정보를 메모리 상에 전부 불러온 상태로 검색하는건 좋지 않을 것 같습니다.

요즘 아무리 메모리 가격기 저렴하다고 해도...
사전이 영한 사전 하나만 있는건 아니니까요.

그리고 정렬 순서로 앞뒤단어 보기라든지 일반적인 사전 프로그램의 기능을 구현하기 쉬운지도 생각해 봐야 할 것 같습니다.

참고 싸이트
http://kibs.kaist.ac.kr/beginner/tool1.htm

ㅡ,.ㅡ;;의 이미지

제가 MS도스시절에 단어장을 만들어본기억있는데요.
그때 10만단어가 좀 덜됬던거 같군요..

실제로 10만건이라는것도 작다고 생각되는 분량인데 너무 거대하게 생각하시는건 아닌지 모르겠습니다.


----------------------------------------------------------------------------

lunarainbow의 이미지

peccavi wrote:

임의의 단어 샘플을 가진 텍스트 파일을 다음과 같이 만들었습니다.

aaaaaaaaaa
aaaaaaaaab
aaaaaaaaac

...

zzzzzzzzzx
zzzzzzzzzy
zzzzzzzzzz

딴지인것 같습니다만, 위 샘플 파일을 통채로 다 만드신 것인가요?

제 생각에는 그 샘플 파일의 크기가 26^10 이 될것 같은데..

141167095653376 byte :roll:

alsong의 이미지

이미 소팅이 다되어 있다면
바이너리 서치(?가운데 반씩 나누어서 검색하는)를 구현하시는것도 괜찮을듯 싶군요..
코드(50줄 정도)도 짧고 검색시간을 20+알파 번 루핑돌면 백만건 중에 하나를 찾을 수 있습니다.

그나저나 백수 언제 탈출하냐... ㅡㅡ; 배고파라.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.