{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T13:55:31Z","timestamp":1762955731716,"version":"3.41.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,6,5]],"date-time":"2017-06-05T00:00:00Z","timestamp":1496620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Ministry of Education, Culture, Sports, Science and Technology (MEXT), Japan; JST, Strategic International Collaborative Research Program, SICORP"},{"name":"CPS-IIP Project"},{"name":"national level challenges \u201cresearch and development for the realization of next-generation IT platforms\u201d by MEXT, Japan"},{"name":"Grant-in-Aid for Scientific Research","award":["2620013"],"award-info":[{"award-number":["2620013"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2018,1,31]]},"abstract":"<jats:p>Inverse Document Frequency (IDF) is widely accepted term weighting scheme whose robustness is supported by many theoretical justifications. However, applying IDF to word N-grams (or simply N-grams) of any length without relying on heuristics has remained a challenging issue. This article describes a theoretical extension of IDF to handle N-grams. First, we elucidate the theoretical relationship between IDF and information distance, a universal metric defined by the Kolmogorov complexity. Based on our understanding of this relationship, we propose N-gram IDF, a new IDF family that gives fair weights to words and phrases of any length. Based only on the magnitude relation of N-gram IDF weights, dominant N-grams among overlapping N-grams can be determined. We also propose an efficient method to compute the N-gram IDF weights of all N-grams by leveraging the enhanced suffix array and wavelet tree. Because the exact computation of N-gram IDF provably requires significant computational cost, we modify it to a fast approximation method that can estimate weight errors analytically and maintain application-level performance. Empirical evaluations with unsupervised\/supervised key term extraction and web search query segmentation with various experimental settings demonstrate the robustness and language-independent nature of the proposed N-gram IDF.<\/jats:p>","DOI":"10.1145\/3052775","type":"journal-article","created":{"date-parts":[[2017,6,7]],"date-time":"2017-06-07T12:47:23Z","timestamp":1496839643000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["IDF for Word N-grams"],"prefix":"10.1145","volume":"36","author":[{"given":"Masumi","family":"Shirakawa","sequence":"first","affiliation":[{"name":"Osaka University, Osaka, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takahiro","family":"Hara","sequence":"additional","affiliation":[{"name":"Osaka University, Osaka, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shojiro","family":"Nishio","sequence":"additional","affiliation":[{"name":"Osaka University, Osaka, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,5]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00065-0"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4573(02)00021-3"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 390--399","author":"Barbay J\u00e9r\u00e9my","year":"2002","unstructured":"J\u00e9r\u00e9my Barbay and Claire Kenyon . 2002 . Adaptive intersection and t-threshold problems . In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 390--399 . J\u00e9r\u00e9my Barbay and Claire Kenyon. 2002. Adaptive intersection and t-threshold problems. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 390--399."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.681318"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28873"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.4630250505"},{"key":"e_1_2_2_7_1","volume-title":"Proceedings of International Conference of the German Society for Computational Linguistics and Language Technology (GSCL). 31--40","author":"Bouma Gerlof","year":"2009","unstructured":"Gerlof Bouma . 2009 . Normalized (pointwise) mutual information in collocation extraction . In Proceedings of International Conference of the German Society for Computational Linguistics and Language Technology (GSCL). 31--40 . Gerlof Bouma. 2009. Normalized (pointwise) mutual information in collocation extraction. In Proceedings of International Conference of the German Society for Computational Linguistics and Language Technology (GSCL). 31--40."},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of International Conference on Computational Linguistics (COLING). 116--124","author":"Bu Fan","year":"2010","unstructured":"Fan Bu , Xiaoyan Zhu , and Ming Li . 2010 . Measuring the non-compositionality of multiword expressions . In Proceedings of International Conference on Computational Linguistics (COLING). 116--124 . Fan Bu, Xiaoyan Zhu, and Ming Li. 2010. Measuring the non-compositionality of multiword expressions. In Proceedings of International Conference on Computational Linguistics (COLING). 116--124."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324900000139"},{"key":"e_1_2_2_10_1","first-page":"1","article-title":"Word association norms, mutual information, and lexicography","volume":"16","author":"Church Kenneth Ward","year":"1990","unstructured":"Kenneth Ward Church and Patrick Hanks . 1990 . Word association norms, mutual information, and lexicography . Comput. Ling. 16 , 1 (Mar. 1990), 22--29. Kenneth Ward Church and Patrick Hanks. 1990. Word association norms, mutual information, and lexicography. Comput. Ling. 16, 1 (Mar. 1990), 22--29.","journal-title":"Comput. Ling."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.844059"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.48"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022627411411"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of Meeting on Mathematics of Language (MOL). 369--381","author":"da Silva Joaquim Ferreira","year":"1999","unstructured":"Joaquim Ferreira da Silva and Jos\u2019e Gabriel Pereira Lopes . 1999 . A local maxima method and a fair dispersion normalization for extracting multi-word units from corpora . In Proceedings of Meeting on Mathematics of Language (MOL). 369--381 . Joaquim Ferreira da Silva and Jos\u2019e Gabriel Pereira Lopes. 1999. A local maxima method and a fair dispersion normalization for extracting multi-word units from corpora. In Proceedings of Meeting on Mathematics of Language (MOL). 369--381."},{"volume-title":"Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 743--752","author":"Demaine Erik D.","key":"e_1_2_2_15_1","unstructured":"Erik D. Demaine , Alejandro L\u00f3pez-Ortiz , and J. Ian Munro . 2000. Adaptive set intersections, unions, and differences . In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 743--752 . Erik D. Demaine, Alejandro L\u00f3pez-Ortiz, and J. Ian Munro. 2000. Adaptive set intersections, unions, and differences. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 743--752."},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of ACM SIGKDD Workshop on Text Mining. 20--23","author":"Dias Ga\u00ebl","year":"2000","unstructured":"Ga\u00ebl Dias . 2000 . Mining textual associations in text corpora . In Proceedings of ACM SIGKDD Workshop on Text Mining. 20--23 . Ga\u00ebl Dias. 2000. Mining textual associations in text corpora. In Proceedings of ACM SIGKDD Workshop on Text Mining. 20--23."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/364520.364540"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972733.6"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.002"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.290948"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850","author":"Grossi Roberto","year":"2003","unstructured":"Roberto Grossi , Ankur Gupta , and Jeffrey Scott Vitter . 2003 . High-order entropy-compressed text indexes . In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850 . Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. 2003. High-order entropy-compressed text indexes. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963423"},{"volume-title":"Handbook of the Poisson Distribution","author":"Haight Frank A.","key":"e_1_2_2_23_1","unstructured":"Frank A. Haight . 1967. Handbook of the Poisson Distribution . Wiley , New York . Frank A. Haight. 1967. Handbook of the Poisson Distribution. Wiley, New York."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.4630260402"},{"key":"e_1_2_2_25_1","volume-title":"Proceedings of International Conference on Computational Linguistics (COLING). 365--373","author":"Hasan Kazi Saidul","year":"2010","unstructured":"Kazi Saidul Hasan and Vincent Ng . 2010 . Conundrums in unsupervised keyphrase extraction: Making sense of the state-of-the-art . In Proceedings of International Conference on Computational Linguistics (COLING). 365--373 . Kazi Saidul Hasan and Vincent Ng. 2010. Conundrums in unsupervised keyphrase extraction: Making sense of the state-of-the-art. In Proceedings of International Conference on Computational Linguistics (COLING). 365--373."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007999900025"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1108\/eb026526"},{"key":"e_1_2_2_28_1","first-page":"369","article-title":"On tables of random numbers","volume":"25","author":"Kolmogorov Andrey","year":"1963","unstructured":"Andrey Kolmogorov . 1963 . On tables of random numbers . Sankhy\u0101 Ser. A 25 (1963), 369 -- 376 . Andrey Kolmogorov. 1963. On tables of random numbers. Sankhy\u0101 Ser. A 25 (1963), 369--376.","journal-title":"Sankhy\u0101 Ser. A"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP). 230--237","author":"Kudo Taku","year":"2004","unstructured":"Taku Kudo , Kaoru Yamamoto , and Yuji Matsumoto . 2004 . Applying conditional random fields to Japanese morphological analysis . In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP). 230--237 . Taku Kudo, Kaoru Yamamoto, and Yuji Matsumoto. 2004. Applying conditional random fields to Japanese morphological analysis. In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP). 230--237."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.110"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3091622.3091662"},{"key":"e_1_2_2_33_1","volume-title":"Vit\u00e1nyi","author":"Li Ming","year":"2009","unstructured":"Ming Li and Paul M. B . Vit\u00e1nyi . 2009 . An Introduction to Kolmogorov Complexity and Its Applications (3rd ed.). Springer , Berlin. Ming Li and Paul M. B. Vit\u00e1nyi. 2009. An Introduction to Kolmogorov Complexity and Its Applications (3rd ed.). Springer, Berlin."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1699510.1699544"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809071"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458137"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP). 404--411","author":"Mihalcea Rada","year":"2004","unstructured":"Rada Mihalcea and Paul Tarau . 2004 . TextRank: Bringing order into texts . In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP). 404--411 . Rada Mihalcea and Paul Tarau. 2004. TextRank: Bringing order into texts. In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP). 404--411."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963192.1963239"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394373.2394418"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.72"},{"key":"e_1_2_2_41_1","volume-title":"Proceedings of International Conference on Language Resources and Evaluation (LREC). 1037--1041","author":"Or\u0103san Constantin","year":"2004","unstructured":"Constantin Or\u0103san , Viktor Pekar , and Laura Hasler . 2004 . A comparison of summarisation methods based on term specificity estimation . In Proceedings of International Conference on Language Resources and Evaluation (LREC). 1037--1041 . Constantin Or\u0103san, Viktor Pekar, and Laura Hasler. 2004. A comparison of summarisation methods based on term specificity estimation. In Proceedings of International Conference on Language Resources and Evaluation (LREC). 1037--1041."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.3115\/1073336.1073340"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1628960.1628964"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367510"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICMLA.2006.50"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1076034.1076095"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1108\/00220410410560582"},{"key":"e_1_2_2_48_1","volume-title":"Proceedings of Text Retrieval Conference (TREC). 109--126","author":"Robertson Stephen","year":"1994","unstructured":"Stephen Robertson , Steve Walker , Susan Jones , Micheline Hancock-Beaulieu , and Mike Gatford . 1994 . Okapi at TREC-3 . In Proceedings of Text Retrieval Conference (TREC). 109--126 . Stephen Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu, and Mike Gatford. 1994. Okapi at TREC-3. In Proceedings of Text Retrieval Conference (TREC). 109--126."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390409"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505671"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2348283.2348401"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609478"},{"key":"e_1_2_2_53_1","volume-title":"McGill","author":"Salton Gerard","year":"1983","unstructured":"Gerard Salton and Michael J . McGill . 1983 . Introduction to Modern Information Retrieval. McGraw-Hill , New York. Gerard Salton and Michael J. McGill. 1983. Introduction to Modern Information Retrieval. McGraw-Hill, New York."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/361219.361220"},{"key":"e_1_2_2_55_1","volume-title":"Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP). 100--108","author":"Schone Patrick","year":"2001","unstructured":"Patrick Schone and Daniel Jurafsky . 2001 . Is knowledge-free induction of multiword unit dictionary headwords a solved problem? In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP). 100--108 . Patrick Schone and Daniel Jurafsky. 2001. Is knowledge-free induction of multiword unit dictionary headwords a solved problem? In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP). 100--108."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741628"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/946247.946751"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.3115\/1119282.1119287"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.3115\/1073445.1073478"},{"key":"e_1_2_2_61_1","volume-title":"Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 434--439","author":"Turney Peter D.","year":"2003","unstructured":"Peter D. Turney . 2003 . Coherent keyphrase extraction via web mining . In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 434--439 . Peter D. Turney. 2003. Coherent keyphrase extraction via web mining. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 434--439."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471602396"},{"key":"e_1_2_2_63_1","volume-title":"Proceedings of AAAI Conference on Artificial Intelligence (AAAI). 855--860","author":"Wan Xiaojun","year":"2008","unstructured":"Xiaojun Wan and Jianguo Xiao . 2008 . Single document keyphrase extraction using neighborhood knowledge . In Proceedings of AAAI Conference on Artificial Intelligence (AAAI). 855--860 . Xiaojun Wan and Jianguo Xiao. 2008. Single document keyphrase extraction using neighborhood knowledge. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI). 855--860."},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/313238.313437"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361684.1361686"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1016791"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1162\/089120101300346787"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2009.02.026"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3052775","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3052775","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:57Z","timestamp":1750217817000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3052775"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,5]]},"references-count":67,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,31]]}},"alternative-id":["10.1145\/3052775"],"URL":"https:\/\/doi.org\/10.1145\/3052775","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"type":"print","value":"1046-8188"},{"type":"electronic","value":"1558-2868"}],"subject":[],"published":{"date-parts":[[2017,6,5]]},"assertion":[{"value":"2016-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}