titles/search_test.go

   1 package titles_test
   2
   3 import (
   4         "fmt"
   5         "github.com/Kovensky/go-anidb/titles"
   6         "os"
   7         "testing"
   8 )
   9
  10 var db = &titles.TitlesDatabase{}
  11
  12 func init() {
  13         if fh, err := os.Open("anime-titles.dat.gz"); err != nil {
  14                 if fh, err = os.Open("anime-titles.dat"); err != nil {
  15                         panic(err)
  16                 }
  17
  18                 db.LoadDB(fh)
  19         }
  20 }
  21
  22 type TestVector struct {
  23         Input string
  24         Limit int
  25         AIDs  []int
  26 }
  27
  28 func TestFuzzySearch(T *testing.T) {
  29         // Each vector goes one step deeper in the fuzzy search stack
  30         vec := []TestVector{
  31                 // no match
  32                 TestVector{Input: "\x00", Limit: -1, AIDs: []int{}},
  33                 // exact
  34                 TestVector{Input: "SAC2", Limit: 1, AIDs: []int{1176}},
  35                 // exact, but in hungarian!
  36                 TestVector{Input: "Varázslatos álmok", Limit: -1, AIDs: []int{235}},
  37                 // prefix words
  38                 TestVector{Input: "Varázslatos", Limit: 3, AIDs: []int{235, 2152, 2538}},
  39                 // suffix words
  40                 TestVector{Input: "A rózsa ígérete", Limit: -1, AIDs: []int{2152}},
  41                 // infix words
  42                 TestVector{Input: "Stand Alone", Limit: 1, AIDs: []int{247}},
  43                 // prefix
  44                 TestVector{Input: "Ghost in t", Limit: 1, AIDs: []int{61}},
  45                 // suffix
  46                 TestVector{Input: "flowne", Limit: 1, AIDs: []int{184}},
  47                 // words, first word first in name
  48                 TestVector{Input: "Kumo Mukou", Limit: -1, AIDs: []int{469}},
  49                 // words, last word last in name
  50                 TestVector{Input: "A titka", Limit: 1, AIDs: []int{303}},
  51                 // words, infix but not contiguous
  52                 TestVector{Input: "Kidoutai 2nd", Limit: 1, AIDs: []int{1176}},
  53                 // strings, first string first in name
  54                 TestVector{Input: "Kouka Kidou", Limit: 1, AIDs: []int{61}},
  55                 // strings, last string last in name
  56                 TestVector{Input: "app Princess", Limit: 1, AIDs: []int{640}},
  57                 // strings, anywhere in this order
  58                 TestVector{Input: "ouka douta", Limit: 2, AIDs: []int{61, 247}},
  59                 // match everything
  60                 TestVector{Input: "", Limit: 1, AIDs: []int{1}},
  61         }
  62
  63         for i, v := range vec {
  64                 res := db.FuzzySearch(v.Input).ResultsByAID()
  65                 if v.Limit > 0 && len(res) > v.Limit {
  66                         res = res[:v.Limit]
  67                 }
  68
  69                 wrong := false
  70                 if len(v.AIDs) != len(res) {
  71                         wrong = true
  72                 } else {
  73                         for j, r := range res {
  74                                 if v.AIDs[j] != r.AID {
  75                                         wrong = true
  76                                 }
  77                         }
  78                 }
  79
  80                 if wrong {
  81                         list := make([]string, 0, len(res))
  82                         for _, r := range res {
  83                                 list = append(list, fmt.Sprintf("%d (%s)", r.AID, r.PrimaryTitle))
  84                         }
  85                         T.Errorf("Vector #%d: Expected AID list %v, got AID list %v", i+1, v.AIDs, list)
  86                 }
  87         }
  88 }
  89
  90 func TestFuzzySearchFold(T *testing.T) {
  91         // Same vector as the previous one, but with disturbed word cases
  92         vec := []TestVector{
  93                 // exact
  94                 TestVector{Input: "sac2", Limit: 1, AIDs: []int{1176}},
  95                 // exact, but in hungarian!
  96                 TestVector{Input: "VarÁzslatos Álmok", Limit: -1, AIDs: []int{235}},
  97                 // prefix words
  98                 TestVector{Input: "varázslatos", Limit: 3, AIDs: []int{235, 2152, 2538}},
  99                 // suffix words
 100                 TestVector{Input: "a rÓzsa ígérete", Limit: -1, AIDs: []int{2152}},
 101                 // infix words
 102                 TestVector{Input: "Stand Alone", Limit: 1, AIDs: []int{247}},
 103                 // prefix
 104                 TestVector{Input: "ghost in t", Limit: 1, AIDs: []int{61}},
 105                 // suffix
 106                 TestVector{Input: "FlownE", Limit: 1, AIDs: []int{184}},
 107                 // words, first word first in name
 108                 TestVector{Input: "kumo mukou", Limit: -1, AIDs: []int{469}},
 109                 // words, last word last in name
 110                 TestVector{Input: "a titka", Limit: -1, AIDs: []int{303}},
 111                 // words, infix but not contiguous
 112                 TestVector{Input: "kidoutai 2nd", Limit: 1, AIDs: []int{1176}},
 113                 // strings, first string first in name
 114                 TestVector{Input: "Kouka kidou", Limit: 1, AIDs: []int{61}},
 115                 // strings, last string last in name
 116                 TestVector{Input: "app princess", Limit: 1, AIDs: []int{640}},
 117                 // strings, anywhere in this order
 118                 TestVector{Input: "Ouka Douta", Limit: 2, AIDs: []int{61, 247}},
 119                 // no match
 120                 TestVector{Input: "\x00", Limit: -1, AIDs: []int{}},
 121         }
 122
 123         for i, v := range vec {
 124                 res := db.FuzzySearchFold(v.Input).ResultsByAID()
 125                 if v.Limit > 0 && len(res) > v.Limit {
 126                         res = res[:v.Limit]
 127                 }
 128
 129                 wrong := false
 130                 if len(v.AIDs) != len(res) {
 131                         wrong = true
 132                 } else {
 133                         for j, r := range res {
 134                                 if v.AIDs[j] != r.AID {
 135                                         wrong = true
 136                                 }
 137                         }
 138                 }
 139
 140                 if wrong {
 141                         list := make([]string, 0, len(res))
 142                         for _, r := range res {
 143                                 list = append(list, fmt.Sprintf("%d (%s)", r.AID, r.PrimaryTitle))
 144                         }
 145                         T.Errorf("Vector #%d: Expected AID list %v, got AID list %v", i+1, v.AIDs, list)
 146                 }
 147         }
 148 }
 149
 150 // exact match of primary title
 151 func BenchmarkFuzzySearch_bestCase(B *testing.B) {
 152         // grep '|1|' anime-titles.dat | cut -d'|' -f4 | sort -R | sed 's/\(.*\)/"\1",/' | \
 153         //    head -n 30
 154         vec := []string{
 155                 "Shin Tennis no Ouji-sama", "Shimai Ningyou", "Aniyome",
 156                 "Dragon Ball Z: Kyokugen Battle!! Sandai Super Saiyajin", "Uchuu Kuubo Blue Noah",
 157                 "Hotaru no Haka", "First Kiss Story: Kiss Kara Hajimaru Monogatari", "Seikai no Senki III",
 158                 "Ikkitousen: Xtreme Xecutor", "Houkago Ren`ai Club: Koi no Etude",
 159                 "DNA2: Dokoka de Nakushita Aitsu no Aitsu (1995)", "Bamboo Blade", "Accelerando",
 160                 "Soukyuu no Fafner: Dead Aggressor", "Eiga Futari wa Precure Max Heart",
 161                 "Kyoufu no Kyou-chan", "Shin Taketori Monogatari: 1000-nen Joou", "Fresh Precure!",
 162                 "Grope: Yami no Naka no Kotori-tachi", "Seitokai Yakuindomo", "Chikyuu Shoujo Arjuna",
 163                 "Choukou Tenshi Escalayer", "Dragon Ball Kai", "Dragon League", "Hatsukoi Limited",
 164                 "Sexfriend", "Ao no Exorcist", "Futatsu no Spica", "Adesugata Mahou no Sannin Musume",
 165                 "Yawara! A Fashionable Judo Girl",
 166         }
 167
 168         B.ResetTimer()
 169         for i := 0; i < B.N; i++ {
 170                 db.FuzzySearch(vec[i%len(vec)])
 171         }
 172 }
 173
 174 // // exact match of x-jat, en or ja non-primary title
 175 // func BenchmarkFuzzySearch_secondBestCase(B *testing.B) {
 176 //      // grep -E '\|3\|(x-jat|en|ja)\|' anime-titles.dat | cut -d'|' -f4 | sort -R | \
 177 //      //    sed 's/\(.*\)/"\1",/' | head -n 30
 178 //      vec := []string{
 179 //              "yosusora", "heartcatch", "chuunibyou", "Stringendo", "おれいも", "yamato 2199",
 180 //              "mai otome zwei", "cg r1", "harem", "Dorvack", "Natsume 1", "SMJA", "SM", "J2",
 181 //              "amstv2", "BJ Movie (2005)", "munto2", "nyc", "MT", "DBZ Movie 2",
 182 //              "Zatch Bell Movie 2", "Armitage", "J0ker", "CH", "sugar", "vga", "Nadesico",
 183 //              "dgc nyo", "setv", "D.g", "マジプリ", "myyour", "Haruhi 2009", "bantorra", "yamato2",
 184 //              "bakuhan", "vk2", "BBB", "5-2", "GSD SE III", "akasaka", "GS SE II", "F3", "おれつば",
 185 //              "sencolle", "wellber", "SailorMoon", "ay", "HCPC", "kxstv", "Shana III",
 186 //      }
 187
 188 //      B.ResetTimer()
 189 //      for i := 0; i < B.N; i++ {
 190 //              db.FuzzySearch(vec[i%len(vec)])
 191 //      }
 192 // }
 193
 194 // // exact match of non-primary title in any other language
 195 // func BenchmarkFuzzySearch_thirdBestCase(B *testing.B) {
 196 //      // grep '|2|' anime-titles.dat | grep -Ev '(x-jat|en|ja)' | cut -d'|' -f4 | \
 197 //      //    sort -R | sed 's/\(.*\)/"\1",/' | head -n 30
 198 //      vec := []string{
 199 //              "Зірка☆Щастя", "La ilusión de triunfar", "La scomparsa di Haruhi Suzumiya",
 200 //              "Код Геас: Бунтът на Люлюш 2", "我的女神 剧场版", "Lamu - Un rêve sans fin",
 201 //              "Lupin III: La cospirazione dei Fuma", "Адовая Девочка дубль 2", "夏娃的时间",
 202 //              "Дівчинка, що стрибала крізь всесвіт", "Мій сусід Тоторо", "机巧魔神",
 203 //              "City Hunter - Flash spécial !? La mort de Ryo Saeba", "Ateştopu", "مسدس×سيف",
 204 //              "Gli amici animali", "沉默的未知", "忧伤大人二之宫", "Пита-Тен", "Глава-гора", "高校龍中龍",
 205 //              "Яблочное зернышко (фильм второй)", "پروکسی مابعد", "青之花", "Heidi, la fille des Alpes",
 206 //              "银盘万花筒", "Temi d`amore tra i banchi di scuola", "Съюзът на Среброкрилите", "Аякаши",
 207 //              "Дух в оболонці: комплекс окремості", "贫乏姊妹物语", "La rose de Versailles",
 208 //              "แฮปปี้ เลสซั่น", "Juodasis Dievas", "Ерата Сенгоку: Последното парти",
 209 //              "Белина: Чезнеща в тъмнината", "Пламенный лабиринт", "Капризный Робот", "Kovboy Bebop: Film",
 210 //              "Bavel`in Kitabı", "东京魔人学院剑风帖 龙龙", "سكول رمبل الفصل الثاني", "青之驱魔师", "سايكانو",
 211 //              "神的记事本", "死神的歌谣", "Angel e a Flor de Sete Cores", "ماگی: هزارتوی جادو", "Spirală",
 212 //              "Chié la petite peste",
 213 //      }
 214
 215 //      B.ResetTimer()
 216 //      for i := 0; i < B.N; i++ {
 217 //              db.FuzzySearch(vec[i%len(vec)])
 218 //      }
 219 // }
 220
 221 // match of initial words
 222 func BenchmarkFuzzySearch_initialWords(B *testing.B) {
 223         // cat anime-titles.dat | cut -d'|' -f4 | grep -E '[^ ]+ [^ ]+ [^ ]+' | \
 224         //     sort -R | cut -d' ' -f1,2 | sed 's/\(.*\)/"\1",/' | head -n 30
 225         vec := []string{
 226                 "To Love", "Utawarerumono -", "Eden of", "D.C.if ～ダ・カーポ", "Вечност над",
 227                 "Rupan Sansei:", "Los Caballeros", "Neko Hiki", "LoGH: A", "Arcadia of",
 228                 "Pokémon 4Ever:", "Lenda Lunar", "Transformers: Master", "Tάρο, ο", "El Puño",
 229                 "El taxi", "Lupin the", "Ah! My", "Le journal", "Odin: Koushi", "Amazing-man: The",
 230                 "Legend of", "Youka no", "Я люблю", "Abe George", "Sisters of", "Ouran High",
 231                 "Batman: Gotham", "Dantalian no", "Koi to", "Night Shift",
 232         }
 233
 234         B.ResetTimer()
 235         for i := 0; i < B.N; i++ {
 236                 db.FuzzySearch(vec[i%len(vec)])
 237         }
 238 }
 239
 240 // match of final words
 241 func BenchmarkFuzzySearch_finalWords(B *testing.B) {
 242         // cat anime-titles.dat | cut -d'|' -f4 | grep -E '^[^ ]+ [^ ]+ [^ ]+ [^ ]+$' | \
 243         //     sort -R | cut -d' ' -f3,4 | sed 's/\(.*\)/"\1",/' | head -n 30
 244         vec := []string{
 245                 "do Zodíaco", "Formula 91", "Shuto Houkai", "Deadly Sins", "gui lai",
 246                 "muistoja tulevaisuudesta", "Mission 1-3", "スペシャルエディションII それぞれの剣", "Một Giây",
 247                 "Meia-Lua Acima", "Mighty: Decode", "To Screw", "do Tênis", "(Duke Fleed)", "Olympic Taikai",
 248                 "Драма ангелов", "Shihosha Judge", "демонов Йоко", "Shoujo Club", "Family (2)", "do Tesouro",
 249                 "Witte Leeuw", "von Mandraguar", "Jin Xia", "Tabi Movie", "Symphonia 2", "no Tenkousei",
 250                 "Movie (2011)", "Guardian Signs", "Você 2",
 251         }
 252
 253         B.ResetTimer()
 254         for i := 0; i < B.N; i++ {
 255                 db.FuzzySearch(vec[i%len(vec)])
 256         }
 257 }
 258
 259 // XXX: This is somehow the most time-consuming case, despite terminating several
 260 // regular expressions earlier than the next two benchmarks.
 261 //
 262 // All regular expressions checked here (besides the .*-peppered one for initial condidate search)
 263 // have no metacharacters at all besides the trivial \A and \z; while the ones for the following
 264 // cases include more complicated grouped expressions...
 265 func BenchmarkFuzzySearch_infixWords(B *testing.B) {
 266         // cat anime-titles.dat | cut -d'|' -f4 | grep -E '^[^ ]+ [^ ]+ [^ ]+ [^ ]+$' | \
 267         //     sort -R | cut -d' ' -f2,3 | sed 's/\(.*\)/"\1",/' | head -n 30
 268         vec := []string{
 269                 "Yes! プリキュア5GoGo!", "Grime X-Rated", "Diễn Ngàn", "Super-Refined Ninja",
 270                 "o Haita", "Conan: 14.", "the Seagulls", "009 Kaijuu", "Monogatari Daini-hen:",
 271                 "no Haha", "по Ловец", "Centimeters per", "wang gui", "the Wandering", "Saru Kani",
 272                 "Dark Red", "Pair: Project", "Охотник на", "trois petits", "of Teacher", "wa Suitai",
 273                 "Lolita Fantasy", "εκατοστά το", "Eri-sama Katsudou", "希望の学園と絶望の高校生 The",
 274                 "Comet SPT", "HUNTER スペシャル", "no Makemono", "Kızı: İkinci", "Pirate Captain",
 275         }
 276
 277         B.ResetTimer()
 278         for i := 0; i < B.N; i++ {
 279                 db.FuzzySearch(vec[i%len(vec)])
 280         }
 281 }
 282
 283 func BenchmarkFuzzySearch_alternatingWords(B *testing.B) {
 284         // cat anime-titles.dat | cut -d'|' -f4 | grep -E '^[^ ]+ [^ ]+ [^ ]+ [^ ]+ [^ ]+$' | \
 285         //     sort -R | cut -d' ' -f2,4 | sed 's/\(.*\)/"\1",/' | head -n 30
 286         vec := []string{
 287                 "of Millennium", "Kreuz: und", "для Літнє", "Saikyou Deshi", "Hearts: no", "Roh Wolf",
 288                 "III: Columbus", "Shin-chan Film", "Ball Superandroid", "恋のステージ=HEART FIRE!",
 289                 "Disease Moon", "Corps Mecha", "BLOOD-C Last", "- trésor", "Lover a", "dievčati, preskočilo",
 290                 "Star: Szomorú", "Ai Marchen", "Kishin &", "Seiya: Goddess", "Orange Shiroi", "Punch Sekai:",
 291                 "No.1: no", "ο του", "プリキュアオールスターズ Stage", "Ankoku Hakai", "8-ма по", "II Ultimate",
 292                 "Tenma Kuro", "Grade Kakusei",
 293         }
 294
 295         B.ResetTimer()
 296         for i := 0; i < B.N; i++ {
 297                 db.FuzzySearch(vec[i%len(vec)])
 298         }
 299 }
 300
 301 func BenchmarkFuzzySearch_worstCase(B *testing.B) {
 302         // cat anime-titles.dat | cut -d'|' -f4 | \
 303         //     perl -MEncode \
 304         //         -pe'chomp; $_ = encode_utf8(substr(decode_utf8($_), 1, -1) . "\n")' | \
 305         //     sort -R | sed 's/\(.*\)/"\1",/' | head -n 30
 306         // further perturbed by hand
 307         vec := []string{
 308                 "ig ray S in han: Den tsu o Yob Amig",
 309                 "ar Ben th Sea: 20.00 Mil for Lov",
 310                 "eminin Famil",
 311                 "界の断",
 312                 "凹内かっぱまつ",
 313                 "ゅーぶら!",
 314                 "unog",
 315                 "aji no ppo: pion Roa",
 316                 "etect boy ma",
 317                 "aruto Movi",
 318                 "光のピア ユメミと銀 バラ騎士",
 319                 "ki ru Sh j",
 320                 "aint : Ο Χαμέ μβάς - Μυθολογία Άδ",
 321                 "as Camarer s Mágica",
 322                 "oll Be Foreve",
 323                 "RAG BALL SODE of BAR",
 324                 "ero eroppi no ken: Pink no",
 325                 "acre east chin Cyg",
 326                 "ister Princes",
 327                 "PRINTS IN SAND",
 328                 "е й хазяї",
 329                 "quent in Dra",
 330                 "inoc chio Bouke",
 331                 "rm Libra : Banto",
 332                 "2 sk sbrutna pojkar äventyrens",
 333                 "タス",
 334                 "last kinė Mažyl",
 335                 "女チャングム 夢 第二",
 336                 "錬金術師 嘆きの丘 の聖なる",
 337                 "hou Rouge Lip"}
 338
 339         B.ResetTimer()
 340         for i := 0; i < B.N; i++ {
 341                 db.FuzzySearch(vec[i%len(vec)])
 342         }
 343 }