The first step self made full text search
Sponsored
·
Your Podcast. Everywhere. Effortlessly.
Share. Educate. Inspire. Entertain. You do you. We'll handle the rest.
→
Your Podcast. Everywhere. Effortlessly.
Share. Educate. Inspire. Entertain. You do you. We'll handle the rest.
→
Share
Embed
The first step self made full text search
ryokato
September 17, 2019
Transcript
72 slides
-
͞ͳ͍͜ͱ w &MBTUJDTFBSDI4PMSͱ͍ͬͨશจݕࡧΤϯδϯΛͬͨݕࡧΞϓϦέʔγϣϯ ͷɾQZUIPOͰ͏UJQT w Γ͍ͨਓ1Z$PO+1ͷൃද ˞ ݟ͍ͯͩ͘͞PSݕࡧٕज़ษڧձ w ͘͠ੋඇۭ͖࣌ؒʹ͠·͠ΐ͏
w ΫϩʔϦϯάεΫϨΠϐϯάʹ͍ͭͯ w ؾʹͳΔਓɺຊΛಡΉPS!TIJOZPSLF͞Μ ˞ !WBBBBBORVJTI͞Μ ˞ ͷϒϩάΛݟͯ ͍ͩ͘͞ w ˞IUUQTTMJEFTIJQDPNVTFST!JLUBLBIJSPQSFTFOUBUJPOT%3+YK,G#'&(43DW:K$"G w ˞IUUQTTIJOZPSLFIBUFOBCMPHDPNFOUSZLPXBLVOBJDSBXMBOETDSBQJOH w ˞IUUQTWBBBBBBORVJTIIBUFOBCMPHDPNFOUSZ -
શจݕࡧʹ͍ͭͯ શจݕࡧͱʁ w lݕࡧͷର͕ʮςΩετ͔ΒͳΔจষͷશ෦ͷจʯͰ͋Δ߹ʹɺͦͷจষʹର ͯ͠ݕࡧΛߦ͏͜ͱz ˞ ݕࡧΤϯδϯͱʁ w lจষͷू߹͔Βɺ୯ޠ࣭ͳͲ͔ΒͳΔใཁٻʹద߹͢ΔจষΛݟ͚ͭΔ
ݕ ࡧ͢Δ ͨΊͷγεςϜιϑτΣΞͷ૯শz ˞ ˞ʮݕࡧΤϯδϯࣗ࡞ೖʯٕज़ධࣾ -
Ͱ࡞ΔQZUIPOͷݕࡧΤϯδϯ def add_text(text: str): with open("db.txt", "a") as f: f.write(text
+ "\n") def search(keyword: str): with open("db.txt", "r") as f: return [l.strip() for l in f if keyword in l] if __name__ == "__main__": texts = [ "Beautiful is better than ugly.", "Explicit is better than implicit.", "Simple is better than complex." ] for text in texts: add_text(text) results = search("Simple") for result in results: print(result) -
શจݕࡧʹ͍ͭͯ (SFQܕ ˞ w ઢܗࠪΛߦ͏ w ݱࡏͷίϯϐϡʔλʔͰɺγΣʔΫεϐΞશू ສޠ نͷจষʹର
ͯ͠ͷ୯७ͳΫΤϦʹରͯ͜͠ΕͰॆͱ͍͏આ͋Δ ˞ ࡧҾ ΠϯσοΫε ܕ ˞ w ͋Β͔͡ΊݕࡧରͱͳΔจॻ܈Λࠪͯ͠ࡧҾσʔλΛ࡞͓ͬͯ͘ ϕΫτϧܕ w ಛϕΫτϧΛ࡞ͯ͠ϕΫτϧؒͷڑΛܭࢉ ˞IUUQTKBXJLJQFEJBPSHXJLJ&"&&"$&#" ˞ʮใݕࡧͷجૅʯڞཱग़൛ -
ࡧҾ ΠϯσοΫε ܕ w ͋Β͔͡ΊݕࡧରͷจॻΛࠪͯ͠ɺࡧҾσʔλΛ४උ͓ͯ͘͠ํ๏ w ࡧҾϑΝΠϧΛ࡞͢Δ͜ͱΛΠϯσΫγϯάɺੜ͞ΕΔσʔλΛΠϯσοΫ εͱ͍͏ w ࡧҾͷ࡞Γํ༷ʑ͋Δ͕ɺҰൠతͳͷసஔΠϯσοΫε
w ଟ͘ͷશจݕࡧΤϯδϯͰ࠾༻͞Ε͍ͯΔ w ΠϝʔδຊͷޙΖʹ͍͍ͭͯΔࡧҾ w Ωʔϫʔυͱϖʔδ -
సஔΠϯσοΫε ٯΠϯσοΫε w ୯ޠͱͦΕؚ͕·Ε͍ͯΔจষͷϚοϐϯάΛอ࣋͢ΔΠϯσοΫεܕͷσʔλ ߏ ˞ w ࣙॻͱϙεςΟϯάͰߏ͞ΕΔ 1ZUIPO
&MBTUJDTFBSDI ࣙॻ ϙεςΟϯά ϙεςΟϯάϦετ ϙεςΟϯά W w ˞XJLJQFEJB w ˞ਤʮใݕࡧͷجૅʯڞཱग़൛ W సஔΠϯσοΫε -
సஔΠϯσοΫεͷΠϯσοΫε୯Ґ w Ϩίʔυ୯ҐసஔΠϯσοΫε w ୯ޠͱ୯ޠΛؚΉจষ จষJE ΛϦετͯ࣋ͭ͠ w JH1ZUIPO<
> w ϝϦοτγϯϓϧͰ࣮͍͢͠ɻσΟεΫ༰ྔ͕গͳ͍ɻ w σϝϦοτػೳੑ͕͍͠ w ୯ޠ୯ҐసஔΠϯσοΫε w ୯ޠͱ୯ޠΛؚΉจষ จষJE Ћͷใ JH୯ޠͷग़ݱҐஔ w JH1ZUIPO< > w ϝϦοτػೳੑ͕ߴ͍ɻྫ͑ϑϨʔζݕࡧ͕Ͱ͖Δɻ w σϝϦοτσΟεΫ༰ྔ͕ଟ͍ɻ w ˞ʮใݕࡧͷجૅʯڞཱग़൛ -
సஔΠϯσοΫε w QZUIPOͰEJDUJPOBSZ w LFZ͕Ұக͠ͳ͚ΕऔಘͰ͖ͳ͍ w Ͳ͏͍͏୯ҐͰΠϯσοΫεΛ࡞͢Δ͔͕ॏཁ సஔΠϯσοΫε 1ZUIPO<
> 1ZUIPOɹ ˓ QZUIPOɹ ✕ 1Zɹ ✕ ύΠιϯɹ ✕ -
ΠϯσοΫεͷநग़ख๏ w ୯ޠׂ τʔΫφΠζ w 8IJUFTQBDF w ܗଶૉղੳ ຊޠ
w /HSBN w γάωνϟ w ඌࣙྻ w FUD -
ܗଶૉղੳ XIJUFTQBDF ͱ/HSBN ܗଶૉղੳ /HSBN τʔΫφΠζ JHʮ౦ژʯʮࣄʯ JHʮ౦ژʯʮژʯʮʯʮࣄʯ τʔΫϯ গͳ͍
ଟ͍ ΠϯσοΫε αΠζ খ͍͞ େ͖͍ ݕࡧ࿙Ε ଟ͍ গͳ͍ ৽ޠରԠ ✕ ˓ ϊΠζ গͳ͍ ଟ͍ -
ΠϯσοΫεੜ w ΠϯσοΫεͷੜ࣌ʹτʔΫφΠζ͚ͩͰͳ͘ςΩετʹॲཧΛՃ͑Δඞཁ ͋Δ w Ͳ͏͍͏ݕࡧΤϯδϯʹ͢Δ͔ґଘ͢Δ w JH)5.-Λݕࡧ͢ΔΤϯδϯ w HPPHMFͷΑ͏ʹίϯςϯπͷΈΛରʹ͢Δ߹
w )5.-λάෆཁɹˠɹɹ)5.-λάΛআڈ͢Δ w (JUIVCͷΑ͏ʹίʔυΛରʹ͢Δ߹ w )5.-λάඞཁ -
ΠϯσοΫεੜॲཧ w ςΩετશମʹॲཧΛՃ͑Δ DIBSpMUFS w JHIUNMλάΛআ͘ খจࣈ େจࣈ ʹ͢Δ
w ༩͑ΒΕͨςΩετΛׂ͢Δ UPLFOJ[FS w ׂ͞ΕͨUPLFOʹॲཧΛՃ͑Δ UPLFOpMUFS w JHਖ਼نԽ͢Δ ετοϓϫʔυΛআ͘ w ͜ΕΒͷॲཧΛ·ͱΊͯ"OBMZ[FSͱΑͿ -
"OBMZ[FSॲཧ $IBSpMUFS 5PLFOJ[FS 5PLFOpMUFS l I 4JNQMFJTCFUUFSUIBODPNQMFY I z lTJNQMFJTCFUUFSUIBODPNQMFYz <lTJNQMFz lJTz lCFUUFSz lUIBOz
lDPNQMFYz> <lTJNQMFz lJTz lCFUUFS HPPEz lUIBOz lDPNQMFYz> <lTJNQMFz lHPPEz lUIBOz lDPNQMFYz> 5FYU 5PLFOT "OBMZ[FS -
w ΠϯσΫγϯάॲཧ จॻΛड͚औΔ จॻΛׂ͢Δ จॻશମʹॲཧ τʔΫϯׂ τʔΫϯ͝ͱʹॲཧ จষτʔΫϯใΛอଘ ϙεςΟϯάϦετΛ࡞ సஔΠϯσοΫεΛߋ৽ɾอଘ
ݕࡧॲཧͷྲྀΕ "OBMZ[FS *OEFYFS 4UPSBHF %PDVNFOU -
w ݕࡧॲཧ ΫΤϦड͚औΓ ΫΤϦύʔε ΠϯσΫγϯά࣌ͷUPLFOͷܗʹଗ ͑Δ ϙεςΟϯάϦετΛऔಘϚʔδ͢ Δ จॻΛऔಘ͢Δ ฒͼସ͑Δ
݁ՌΛฦ͢ ݕࡧॲཧͷྲྀΕ 1BSTFS "OBMZ[FS GFUDI 4PSUFS 2VFSZ 3FTVMUT .FSHF -
γϯϓϧͳݕࡧΤϯδϯΛ࡞Δ w ཁ݅ w QZDPOKQͷτʔΫΛݕࡧͰ͖Δ w 5JUMFͱৄࡉ w ཧݕࡧ BOEPSOPU
ʹରԠ w ݁ՌείΞ 5'*%' ॱʹฦ͢ w ϑϨʔζݕࡧରԠ͠ͳ͍ w ෳϑΟʔϧυͷݕࡧରԠ͠ͳ͍ w υΩϡϝϯτͷߋ৽͠ͳ͍ w ్தͰυΩϡϝϯτͷՃΛ͠ͳ͍ -
"OBMZ[FS࣮ w ӳޠͱຊޠͦΕͧΕͷ"OBMZ[FSΛ࡞ w ڞ௨ w IUNMλάআ֎ w ετοϓϫʔυআ֎ w
ΞϧϑΝϕοτͯ͢খจࣈʹม w TUFBNJOHॲཧ w JHEPHTˠEPH w ຊޠ w ܗଶૉղੳׂ w ॿࢺɾ෭ࢺɾه߸আ֎ w ӳޠ w 8IJUFTQBDFׂ w ॿࢺετοϓϫʔυͰରԠ -
$IBSpMUFS w ڞ௨ͷΠϯλʔϑΣΠεΛ࡞ w ਖ਼نදݱͰIUNMλάΛআڈ w ΞϧϑΝϕοτΛMPXFSDBTFʹม class CharacterFilter: @classmethod
def filter(cls, text: str): raise NotImplementedError class HtmlStripFilter(CharacterFilter): @classmethod def filter(cls, text: str): html_pattern = re.compile(r"<[^>]*?>") return html_pattern.sub("", text) class LowercaseFilter(CharacterFilter): @classmethod def filter(cls, text: str): return text.lower() -
5PLFOJ[FS w ڞ௨ͷΠϯλʔϑΣΠεΛ४උ w ܗଶૉղੳʹ+BOPNFΛ༻ w ҙ w +BOPNFͷ5PLFOJ[FSΦϒδΣΫτͷ ॳظԽίετ͕ߴ͍ͨΊɼΠϯελ
ϯεΛ͍ճ͢ɻ ˞ from janome.tokenizer import Tokenizer tokenizer = Tokenizer() class BaseTokenizer: @classmethod def tokenize(cls, text): raise NotImplementedError class JanomeTokenizer(BaseTokenizer): @classmethod def tokenize(cls, text): return (t for t in cls.tokenizer.tokeniz e(text)) class WhitespaceTokenizer(BaseTokenizer): @classmethod def tokenize(cls, text): return (t[0] for t in re.finditer(r"[^ \ t\r\n]+", text)) ˞IUUQTHJUIVCDPNNPDPCFUBKBOPNF ˞IUUQTNPDPCFUBHJUIVCJPKBOPNFUPLFOJ[FS -
5PLFOpMUFS w ڞ௨ͷΠϯλʔϑΣΠεΛ४උ w 104'JMUFSͷ߹্UPLFOҾTUSͱ KBOPNFͷUPLFOΦϒδΣΫτΛࢦఆ STOPWORDS = ("is", "was",
"to", "the") def is_token_instance(token): return isinstance(token, Token) class TokenFilter: @classmethod def filter(cls, token): """ in: sting or janome.tokenizer.Token """ raise NotImplementedError class StopWordFilter(TokenFilter): @classmethod def filter(cls, token): if isinstance(token, Token): if token.surface in STOPWORDS: return None if token in STOPWORDS: return None return token -
5PLFOpMUFS w 4UFNJOHॲཧ w ୯ޠͷޠװΛऔΓग़͢ॲཧ w JHʮEPHTʯˠʮEPHʯ w OMULTUFNύοέʔδΛར༻ ˞
from nltk.stem.porter import PorterStemmer ps = PorterStemmer() class Stemmer(TokenFilter): @classmethod def filter(cls, token: str): if token: return ps.stem(token) ˞IUUQXXXOMULPSHBQJOMULTUFNIUNM -
5PLFOpMUFS w 104'JMUFS w ಛఆͷࢺΛআ֎͢Δ w KBOPNFͷUPLFOΦϒδΣΫτͷ QBSU@PG@TQFFDIͰఆ class POSFilter(TokenFilter):
""" ຊޠͷॿࢺ/ه߸Λআ͘ϑΟϧλʔ """ @classmethod def filter(cls, token): """ in: janome token """ stop_pos_list = ("ॿࢺ", "෭ࢺ", "ه߸") if any([token.part_of_speech.startswith(pos) for pos in stop_pos_list]): return None return token -
"OBMZ[FS w #BTFDMBTT w ΫϥεมͰࢦఆͰ͖ΔΑ͏ʹ͢Δ w UPLFOJ[FS w DIBSpMFS
w UPLFO@pMUFS w pMUFSෳࢦఆ͢ΔͨΊྻ w લ͔Βॱ൪ʹॲཧ͍ͯ͘͠ class Analyzer: tokenizer = None char_filters = [] token_filters = [] @classmethod def analyze(cls, text: str): text = cls._char_filter(text) tokens = cls.tokenizer.tokenize(text) filtered_token = (cls._token_filter(token) for t oken in tokens) return [parse_token(t) for t in filtered_token i f t] @classmethod def _char_filter(cls, text): for char_filter in cls.char_filters: text = char_filter.filter(text) return text @classmethod def _token_filter(cls, token): for token_filter in cls.token_filters: token = token_filter.filter(token) return token -
"OBMZ[FS w ݸผͷ"OBMZ[FS w ຊޠ༻ͷ+BQBOFTF5PLFOJ[FS w ӳޠ༻ͷ&OHMJTI5PLFOJ[FS w ͔ΜͨΜʹผͷ"OBMZ[FS࡞Մೳ class
JapaneseAnalyzer(Analyzer): tokenizer = JanomeTokenizer char_filters = [HtmlStripFilter, LowercaseFilter] token_filters = [StopWordFilter, POSFilter, Stemmer] class EnglishAnalyzer(Analyzer): tokenizer = WhitespaceTokenizer char_filters = [HtmlStripFilter, LowercaseFilter] token_filters = [StopWordFilter, Stemmer] -
*OEFYFS w จষΛड͚औΓసஔΠϯσοΫεΛ࡞ w ϝϞϦ্ʹҰ࣌తͳసஔΠϯσοΫε EJDUJPOBZ Ͱอ࣋ w ϝϞϦ্ʹҰఆͷసஔΠϯσοΫε͕ ཷ·ͬͨΒετϨʔδʹอଘ
class InvertedIndex: def __init__( self, token_id: int, token: str, postings_list=[ ], docs_count=0 ) -> None: self.token_id = token_id self.token = token self.postings_list = [] self.__hash_handle = {} self.docs_count = 0 def add_document(doc: str): """ υΩϡϝϯτΛσʔλϕʔεʹՃ͠సஔΠϯσοΫεΛߏங͢Δ """ if not doc: return # # จॻIDͱจষ༰ΛجʹϛχసஔΠϯσοΫε࡞ text_to_postings_lists(doc) # # # ҰఆͷυΩϡϝϯτ͕ϛχసஔΠϯσοΫε͕ཷ·ͬͨΒ Ϛʔδ if len(TEMP_INVERT_INDEX) >= LIMIT: for inverted_index in TEMP_INVERT_INDEX.values() : save_index(inverted_index) -
*OEFYFS w ϙεςΟϯάϦετͷ࡞ w BOBMZ[FSͰUPLFOΛ࡞ w είΞܭࢉͷͨΊจॻதͷτʔΫϯ૯Λ͋ Β͔͡Ίܭࢉ͓ͯ͘͠ w ʮ୯ޠ୯ҐసஔΠϯσοΫεʯ࡞
w ϑϨʔζݕࡧΛ͠ͳ͍ͨΊ w ͨͩ͠ɺείΞܭࢉͷͨΊͦͷτʔΫϯ͕จ ॻதʹ͍ͭ͋͘Δ͔ܭࢉͯ͠ΠϯσοΫεʹ ͓ͬͯ͘ w 1ZUIPO<EPD EPD> def text_to_postings_lists(text) -> list: """ จষ୯ҐͷసஔϦετΛ࡞Δ """ tokens = JapaneseAnalyzer.analyze(text) token_count = len(tokens) document_id = save_document(text, token_count) cnt = Counter(tokens) for token, c in cnt.most_common(): token_to_posting_list(token, document_id, c) def token_to_posting_list(token: str, document_id: int, token_count: int): """ token͔Βposting listΛ࡞Δ """ token_id = get_token_id(token) index = TEMP_INVERT_INDEX.get(token_id) if not index: index = InvertedIndex(token_id, token) posting = "{}: {}".format(str(document_id), str(token_count)) index.add_posting(posting) TEMP_INVERT_INDEX[token_id] = index -
*OEFYFS࡞Πϝʔδ w EPDVNFOU w EPDʮࢲࢲͰ͢ɻʯ w EPDʮࢲͱQZUIPOɻʯ w 5PLFO w
UPLFOࢲ w UPLFOQZUIPO w τʔΫϯ w EPD w EPD w ϙεςΟϯάϦετ w 1ZUIPO<> w ࢲ< > -
ϙεςΟϯάϦετJEॱʹιʔτ͢Δ w ݕࡧͷޮతʹߦ͏ͨΊ w ࠓճͷ࣮Ͱ৮Εͳ͍ w JHεΩοϓϙΠϯλʔ ˞ w
ࠓճVQEBUF͠ͳ͍ͷͰBQQFOE͢Δ͚ͩͰ0, ˞ʮใݕࡧͷجૅʯڞཱग़൛ -
4UPSBHF w ࠓճTRMJUFTRMBMDIFNZΛ༻ w ͳΜͰ͍͍ w /P42-Λ͏ͱָ w ࠓճۃྗQZUIPO͚ͩࡁΉΑ͏ʹ͢ΔͨΊTRMJUFΛ࠾༻ w
ΑΓޮΛٻΊΔͳΒࣗͰ࣮͢Δඞཁ͕͋Δ -
4UPSBHF w σʔλϕʔεεΩʔϚ w %PDVNFUTUBCMFʹςΩετΛอଘ w ݕࡧରͷϑΟʔϧυͷςΩετΛUFYU ϑΟʔϧυͰอ͓࣋ͯ͘͠ class Documents(Base):
__tablename__ = "documents" id = Column(Integer, primary_key=True) text = Column(String) token_count = Column(Integer) date = Column(String) time = Column(String) room = Column(String) title = Column(String) abstract = Column(String) speaker = Column(String) self_intro = Column(String) detail = Column(String) session_type = Column(String) class Tokens(Base): __tablename__ = "tokens" id = Column(Integer, primary_key=True) token = Column(String) class InvertedIndexDB(Base): __tablename__ = "index" id = Column(Integer, primary_key=True) token = Column(String) postings_list = Column(String) docs_count = Column(Integer) token_count = Column(Integer) -
4UPSBHF w σʔλϕʔεॲཧͳͲͷVUJMTؔΛ࣮ w τʔΫϯͷՃɾऔಘ w υΩϡϝϯτͷՃɾऔಘ w సஔΠϯσοΫεͷՃɾߋ৽ɾऔಘ def
add_token(token: str) -> int: SESSION = get_session() token = Tokens(token=token) SESSION.add(token) SESSION.commit() token_id = token.id SESSION.close() return token_id def fetch_doc(doc_id): SESSION = get_session() doc = SESSION.query(Documents).filter(Documents.id = = doc_id).first() SESSION.close() if doc: return doc else: return None -
4FBSDIFS w RVFSZΛड͚औͬͯ w ΫΤϦͷύʔε 1BSTFS"OBMZ[FS w ݁ՌͷEPD@JEΛऔಘ .FSHFS
w จষΛετϨʔδ͔Βऔಘ 'FUDIFS w είΞॱʹฒͼସ͑Δ 4PSUFS def search_by_query(query): if not query: return [] # parse parsed_query = tokenize(query) parsed_query = analyzed_query(parsed_query) rpn_tokens = parse_rpn(parsed_query) # merge doc_ids, query_postings = merge(rpn_tokens) print(doc_ids, query_postings) # fetch docs = [fetch_doc(doc_id) for doc_id in doc_ids] # sort sorted_docs = sort(docs, query_postings) return [_parse_doc(doc) for doc, _ in sorted_docs] -
ٯϙʔϥϯυه๏ ޙஔه๏ w ԋࢉࢠΛඃԋࢉࢠͷޙΖʹஔ͘ه๏ ˞ w JH w ʮ
ʯˠʮ ʯ w ʮ ʯˠʮ ʯ w ʮQZUIPO"/%ݕࡧʯˠʮQZUIPOݕࡧ"/%ʯ w ϝϦοτ w ࣜͷධՁ ܭࢉ ͕γϯϓϧʹͳΔ w ઌ಄͔ΒධՁ͢Δ͚ͩͰࡁΉ w ˞XJLJQFEJBIUUQTKBXJLJQFEJBPSHXJLJ &&%&#$&"&#&&"& # -
1BSTFS import re REGEX_PATTERN = r"\s*(\d+|\w+|.)" SPLITTER = re.compile(REGEX_PATTERN) LEFT
= True RIGHT = False OPERATER = {"AND": (3, LEFT), "OR": (2, LEFT), "NOT": (1 , RIGHT)} def tokenize(text): return SPLITTER.findall(text) def parse_rpn(tokens: list): ɹɹɹ# ΞϧΰϦζϜͷ࣮ • ΞϧΰϦζϜΛ࣮ • தஔه๏Λޙஔه๏ʹ͢Δ͚ͩͳͷͰ࣮ ͢Δͷจࣈྻͱԋࢉࢠ ׅހͷΈ • ਖ਼نදݱͰεϖʔεͱׅހͰׂ • JH<l"z l"/%z l l l#z 03l l$z l z> • ར༻͢ΔΦϖϨʔλʔͱɺͦͷ༏ઌɺ ݁߹ํ๏Λࢦఆ • ༏ઌ • /05 03 "/% • ݁߹ • "/% 03ࠨ݁߹ • /05ӈ݁߹ • ʮ""/% #03$ ʯ • ɹˠɹ<" # $ 03 "/%> -
"OBMZ[FS w సஔΠϯσοΫε࡞࣌ʹࣙॻʹͬ ͨUPLFOͰݕࡧ͢Δඞཁ͕͋Δ w *OEFY࣌ʹͬͨ"OBMZ[FSΛͦͷ··ͬ ͯ0, w +BQBOFTF5PLFOJ[FSͱ&OHMJTI5PLFOJ[FS ʹରԠ͢Δ
w ݕࡧ࣌ʹӳ୯ޠͰݕࡧ w 8IJUFTQBDFUPLFOJ[FSߟྀ͠ͳ͍ w ࠓճׂ͞ΕͨτʔΫϯΛ03ݕࡧ ͱͯ͠ѻ͏ w ʮػցֶश"/%QZUIPOʯ w ˠʮػց03ֶश"/%QZUIPOʯ w ٯϙʔϥϯυه๏มલʹ"OBMZ[F͢ Δ def analyzed_query(parsed_query): return_val = [] for q in parsed_query: if q in OPRS: return_val.append(q) else: analyzed_q = JapaneseAnalyzer.analyze(q) if analyzed_q: tmp = " OR ".join(analyzed_q) return_val += tmp.split(" ") return return_val -
ٯϙʔϥϯυه๏ධՁ w ࡞ͨ͠ٯϙʔϥϯυه๏ΛධՁ͍ͯ͘͠ w खॱ w ʮ ʯ
ͷ߹ ඃԋࢉࢠͷ߹ ԋࢉࢠ ̏ ΛελοΫʹੵΉTUBDL<̏> ඃԋࢉࢠͷ߹ ԋࢉࢠ ̐ ΛελοΫʹੵΉTUBDL<̏ ̐> ԋࢉࢠͷ߹ τοϓ̎ͭΛελοΫ͔ΒऔΓग़͢TUBDL<> ܭࢉ ̏ʴ̐ ͯ͠ελοΫʹੵΉTUBDL<̓> ඃԋࢉࢠͷ߹ ԋࢉࢠ ̍ ΛελοΫʹੵΉTUBDL<̓ ̍> ඃԋࢉࢠͷ߹ ԋࢉࢠ ̎ ΛελοΫʹੵΉTUBDL<̓ ̍ ̎> ԋࢉࢠͷ߹ τοϓ̎ͭΛελοΫ͔ΒऔΓग़͢TUBDL<̓> ܭࢉ ̍̎ ͯ͠ελοΫʹੵΉTUBDL<̓ ̍> ԋࢉࢠͷ߹ τοϓ̎ͭΛελοΫ͔ΒऔΓग़͢TUBDL<> ܭࢉ ̓ ̍ ͯ͠ελοΫʹੵΉTUBDL<̓> -
ٯϙʔϥϯυه๏ධՁ w .FSHF ٯϙʔϥϯυه๏ͷධՁ w ٯϙʔϥϯυه๏ͷධՁ̏ύλʔϯ w ʮελοΫʹੵΉʯɺʮελοΫ͔ΒऔΓग़͢ʯɺʮܭࢉ͢Δʯ w ܭࢉ̎ͭͷඃԋࢉࢠͷධՁͰ͢Ή w
̎ͭͷτʔΫϯͷϙεςΟϯάϦετΛϚʔδ͢Δ w ελοΫʹɺτʔΫϯ͔Βऔಘͨ͠ϙεςΟϯάϦετΛՃ͢Δ -
.FSHF w ٯϙʔϥϯυه๏ධՁखॱ௨Γʹ࣮ w UPLFO͕ඃԋࢉࢠ τʔΫϯͷ߹ʹ ϙεςΟϯάϦετΛऔಘޙTUPDLʹ Ճ w UPLFO͕ԋࢉࢠͷ߹ɺTUPDL͔Β UPQ̎ͭΛऔΓग़ͯ͠NFSHFޙTUPDL
ʹՃ w ϙεςΟϯάϦετείΞܭࢉΑ͏ ʹEJDUJPOBSZͰཧ def merge(tokens: list): target_posting = {} stack = [] for token in tokens: if token not in OPRS: token_id = get_token_id(token) postings_list = fetch_postings_list(token_id ) # scoreܭࢉ༻ʹอ࣋ target_posting[token] = postings_list # doc_idͷΈΛstackʹՃ doc_ids = set([p[0] for p in postings_list]) stack.append(doc_ids) # token͕operaterͩͬͨ߹ else: if not stack: raise if len(stack) == 1: # NOTͷΈڐ༰ if token == "NOT": # NOTͷॲཧ return not_doc_ids, {} else: raise doc_ids1 = stack.pop() doc_ids2 = stack.pop() stack.append(merge_posting(token, doc_ids1, doc_ids2)) -
.FSHF w ʮ/05IPHFʯͷରԠ w ඃԋࢉࢠ̎ͭͷධՁҎ֎ͷධՁํ๏Λ/05 ͷΈڐՄ w UPLFO͕ԋࢉࢠͷ߹ʹTUBDLͷαΠζͱ UPLFOͷதͰఆ #
ʮNOT hogeʯରԠ if len(stack) == 1: # NOTͷΈڐ༰ if token == "NOT": # NOTͷॲཧ doc_ids = stack.pop() not_doc_ids = fetch_not_docs_id(doc_ids) return not_doc_ids, {} else: raise -
.FSHF w ΦϖϨʔλʔΛϢʔβʔ͕هड़͠ͳ͍ ߹ͷରԠ w ʮQZUIPOػցֶशʯ w ˠʮQZUIPO03ػցֶशʯ w
ˠʮQZUIPO"/%ػցֶशʯ w ࠓճ03Λ࠾༻ w ΦϖϨʔλʔΛهड़͠ͳ͍ ඃԋࢉࢠ ͱධՁͷ͕߹Θͳ͍ w ࠷ޙ·ͰධՁͯ͠TUBDL͕̎ͭҎ্͋Δ w શͯͷτʔΫϯΛ࣮ͨ͋͠ͱʹTUBDL ͕ʹͳΔ·Ͱ03NFSHFΛ܁Γฦ͢ for token in tokens: # ධՁॲཧ while len(stack) != 1: doc_ids1 = stack.pop() doc_ids2 = stack.pop() stack.append(merge_posting("OR", doc_ids1, doc_ids2) ) -
είΞϦϯά w 5'*%' w 5'UFSNGSFRVFODZ w จॻதͷ୯ޠͷׂ߹ w ୯ޠ
U จষதͷ୯ޠ 5 w J%'JOWFSUEPDVNFOUGSFRVFODZ w શจॻதͷͦͷ୯ޠΛؚΉจষͷׂ߹ w MPH ͦͷ୯ޠΛؚΉจॻ % શจॻ " w จষதʹΑ͘ग़͖ͯͯɺଞͷจষʹͰͯ͜ͳ͍ͷ΄ͲείΞ͕ߴ͍ -
είΞϦϯά w ݕࡧʹ͓͍ͯͷ*%' w Ωʔϫʔυ͚ͩͰݕࡧ͢Δͱશจจॻͷ*%'ಉ͡ w 5'͚ͩͰΑͦ͞͏ w ͨͩ͠ɺ"/%
03Ͱݕࡧͨ͠ͱ͖ʹҙຯ͕มΘͬͯ͘Δɻ w ෳͷΫΤϦʹର͢Δจॻ܊ͷൺֱͷͨΊͷॏΈ͚ͱߟ͑Δ w ʮ""/%#ʯͰݕࡧͨ͠ͱ͖ͷจॻЋͷ5'*%' w จॻЋͷ5'*%' ΫΤϦ"ͷ5'*%' ΫΤϦ#ͷ5'*%' -
4PSUFS w είΞܭࢉʹ͏΄΅ΠϯσοΫ ε࣌ʹूܭ͍ͯ͠ΔͷΛ͏ w จॻதͷݕࡧτʔΫϯ U w QPTUJOHͰอ࣋
w w จॻதͷτʔΫϯ 5 w %PDVNFOUTอଘ࣌ʹҰॹʹอଘ w EPDUPLFO@DPVOU w ݕࡧτʔΫϯ U ΛؚΉจॻ % w UͷϙεςΟϯάϦετͷ͞ w શจॻ " w %PDVNFOUTUBCMFͷΧϯτ def sort(doc_ids, query_postings): docs = [] all_docs = count_all_docs() for doc_id in doc_ids: doc = fetch_doc(doc_id) doc_tfidf = 0 for token, postings_list in query_postings.items (): idf = math.log10(all_docs / len(postings_lis t)) + 1 posting = [p for p in postings_list if p[0] == doc.id] if posting: tf = round(posting[0] [1] / doc.token_count, 2) else: tf = 0 token_tfidf = tf * idf doc_tfidf += token_tfidf docs.append((doc, doc_tfidf)) return sorted(docs, key=lambda x: x[1], reverse=True ) -
σϓϩΠ5JQT w ϝϞϦΛଟΊʹ͢Δ w ੑೳ͕͕͋Δ w +BOPNF͕QJQͷϏϧυ࣌ʹ.#d.#ఔϝϞϦ͕ඞཁ ˞ w
IFSPLVݫ͍͠ w GSFFɾIPCZ✕ w 4UBOEBSE͓ͦΒ͘✕ w &$UNJDSP✕ w &$UTNBMM˓ w ˞IUUQTNPDPCFUBHJUIVCJPKBOPNF -
վળ w ΠϯσΫγϯάɾݕࡧͷվળ w ϙεςΟϯάϦετͷѹॖ w ޮͷ͍͍ΞϧΰϦζϜͱσʔλߏΛ͏ w ಈతͳΠϯσοΫεͷ࡞ w
ΫΤϦ֦ு w ϑϨʔζݕࡧ w ෳϑΟʔϧυରԠ w ԋࢉࢠͷ֦ு w ετϨʔδ෦ ϑΝΠϧγεςϜ ࣮ w ϕΫτϧݕࡧ w ࢄԽ w FUD -
վળͷͨΊͷࢀߟࢿྉ w ॻ੶ w ʮݕࡧΤϯδϯࣗ࡞ೖʯٕज़ධࣾ w ʮใݕࡧͷجૅʯڞཱग़൛ w ʮߴจࣈྻղੳͷੈքʯؠॻళ w
ʮ%FFQ-FBSOJOHGPS4FBSDIʯ."//*/( w 044 w ʮ8IPPTIʯ w IUUQTCJUCVDLFUPSHNDIBQVUXIPPTITSDEFGBVMUEPDT TPVSDFJOUSPSTU w ʮ&MBTUJDTFBSDIʯ w IUUQTHJUIVCDPNFMBTUJDFMBTUJDTFBSDI w ʮ"QBDIF-VDFOFʯ w IUUQMVDFOFBQBDIFPSHDPSFEPDVNFOUBUJPOIUNM -
·ͱΊ w ݕࡧΤϯδϯͷΈͷઆ໌͔ΒجຊతͳݕࡧΤϯδϯͷ࣮·Ͱઆ໌ͨ͠ w ୯७ʹݟ͑ΔݕࡧΤϯδϯ࣮͢Δͱ৭ʑߟ͑Δ͜ͱ͕͋Δ w ษڧɾझຯʹ͓͍ͯंྠ࠶ൃ໌༗ҙٛ w ݕࡧΤϯδϯΛ࡞Δͷָ͍͠ w
ΈΜͳͰʮ΅͘ͷ͔Μ͕͍͖͑ͨ͞ΐ͏ͷݕࡧΤϯδϯʯΛ࡞Γ·͠ΐ͏
ryook
sferik
tenderlove
bluesmoon
jacobian
mkilby
kastner
uxyall
chriscoyier
rasmusluckow
tomoyanonymous
reverentgeek
lcolladotor
