현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

스트링 판별에 효율적인 해쉬함수설계?

down7town의 이미지
글쓴이: down7town / 작성시간: 토, 2003/08/09 - 4:06오후

웹서버의 로그를 통계적으로 분석하는 프로그램을 만들고 있습니다.

서버내의 URL들간이 통계를 위해서 트리를 이용하고자 하는데, 각 노드에는

디렉토리나 파일이름이 들어가서 계층적 구조를 이루고, 이런 구조는 여러가지 통계적 접근이 가능하게 하거든요..

문제는 각노드들을 서칭할때 스트링을 통째로 비교하는것 보다 해쉬를 사용하는게(키값을 순서적으로 배열해서 일종에 소팅으로 놓고 접근합니다. 키값보다 커버리면 그위치에서 바로 노드를 만들어 버리죠..)좋을것 같아서요. 아무래도 인덱싱에서 빠르니깐요..

디렉토리 이름이나 파일이름으로 해슁할수 있는 해쉬함수? 추천이나 간단히
여러분의 생각을 도움 받고 싶네요.

Forums: 
프로그래밍 QnA
urmajest의 이미지

글쓴이: urmajest / 작성시간: 일, 2003/08/10 - 8:30오전

Quote:
(키값을 순서적으로 배열해서 일종에 소팅으로 놓고 접근합니다. 키값보다 커버리면 그위치에서 바로 노드를 만들어 버리죠..)

왜 키값보다 크면 그 위치에서 노드를 만드나요? -_-

(틀린 것 같다는게 아니구 제가 잘 이해할 수 없다는 말이예요 -_-)

목표는 빠른 속도를 내는 것이고, matching할 스트링이 많아지면

그 수에 비례해서 검색시간이 길어지니깐( O(N) ) 그걸 해쉬를 이용해

해결하시겠다는거죠?

Bloom filter를 추천합니다

직접 설계를 하셔야 할 것 같고요, 구현은 간단합니다.

자세한건 ACM에서 bloom filter로 검색해 보시면 성능에 대한 실험이나

어떻게 사용할 지에 대한 많은 논문이 있구요 (comm쪽에 있습니다)

처음으로 bloom filter를 제안한 논문은 1970년 Burton H.Bloom이라는

사람이 역시 ACM 에 발표했습니다.

기본적으로 (해쉬 베이스드 알고리즘 인지라..) space/time tradeoff를

잘 맞춰줘야합니다.

bloom filter는 free-text search, dictionary search등에 응용이 되곤

한답니다.

그냥 참고하세요 -_-

down7town의 이미지

글쓴이: down7town / 작성시간: 일, 2003/08/10 - 3:06오후

설명이 좀 부족했군요... 다시 설명을 드리면..

트리의 형재 노드들이 키값이 오름차순으로 정열되어 있다고 가정하면
현재 들어온 데이타의 key 값이 4라고 하고 지금 노드들에는 4를 키값으로 가지고 있는것이 없습니다. 즉 처음 들어온 값이라고 보면 되죠.. 만약에 4가 존재하면 거기에 접근할 거고 , 그렇지 않으면 만들어야 하는데, 그 위치를 3과 5사이(3과 5가 존재한다고 가정하면) 에 집어 넣는다는 말이죠..

소팅 해놓으면 현재 노드들에게 없는 키값이 들어 왔을때 무조건 끝까지 검색해봐야 하는 소팅 해놓지 않은 경우보다 빠르잖아요...^^ ;

atlacpi의 이미지

글쓴이: atlacpi / 작성시간: 월, 2003/08/11 - 1:41오전

이럴경우는 file_name의 분포를 어느정도는 할고 있어야겠죠..
가령 a~d로 시작하는 file_name이 많다면, 이지역을 세분화 하고 다른부분은 거의 통합하는 식으로..

또는, file_name의 길이가 같다면. 예로, 8.3으로 통일 되어 있다면 8글자의 ascii값을 모두 더한값의 대략적 분포를 확인하고 해슁하는 방법도 있겠죠...

이렇게 분포만 알면 해슁은 간단해 집니다. 그냥
"val >> 8" 이렇게 쉬프트만 시켜도 256해슁 헤드를 인덱싱 할 수 있으니까요.. #define하나 해놓으면 되죠..--;

근데 찾을 노드가 별로 없으면 해슁 안하는게 나은 겁니다. 몇천개 정도 되면 256해슁이면 1/256로 찾는 시간이 단축되지만 넘작으면 오히려 해슁을 위한 linked-list구현하느라고 오버헤드가 커질지도 몰겠네요..

Vm~*

mach의 이미지

글쓴이: mach / 작성시간: 월, 2003/08/11 - 2:31오후

down7town wrote:
웹서버의 로그를 통계적으로 분석하는 프로그램을 만들고 있습니다.

서버내의 URL들간이 통계를 위해서 트리를 이용하고자 하는데, 각 노드에는

디렉토리나 파일이름이 들어가서 계층적 구조를 이루고, 이런 구조는 여러가지 통계적 접근이 가능하게 하거든요..

문제는 각노드들을 서칭할때 스트링을 통째로 비교하는것 보다 해쉬를 사용하는게(키값을 순서적으로 배열해서 일종에 소팅으로 놓고 접근합니다. 키값보다 커버리면 그위치에서 바로 노드를 만들어 버리죠..)좋을것 같아서요. 아무래도 인덱싱에서 빠르니깐요..

디렉토리 이름이나 파일이름으로 해슁할수 있는 해쉬함수? 추천이나 간단히
여러분의 생각을 도움 받고 싶네요.

* 전산서적 고전(1992년~94년정도)들을 보면 많이 나오는 역파일 알고리즘(검색엔진등에서 많이 사용됨)들을 참조하시는것도 좋은듯 보입니다. 이를테면 FAST-INV라던가, 아니면 trie같은 것도 좋겠습니다. 그냥 참고만 하세요.

------------------ P.S. --------------
지식은 오픈해서 검증받아야 산지식이된다고 동네 아저씨가 그러더라.

댓글 달기

텍스트 포맷에 대한 자세한 정보

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.