Псевдоматричный фильтр Блума для задач быстрого сравнения текстов

Псевдоматричный фильтр Блума для задач быстрого сравнения текстов

Автор: Цхай А.А., Бутаков С.В., Дягилев В.В.

Журнал: Вестник Алтайской академии экономики и права @vestnik-aael

Рубрика: Прикладные исследования социально-экономических процессов

Статья в выпуске: 4 (31), 2013 года.

Бесплатный доступ

Предложена новая структура данных, предназначенная для быстрого сравнения текстов на основе матричных фильтров Блума. Данная структура характеризуется сниженными требованиями к объему памяти при сохранении быстродействия. Тестирование на двух реальных наборах данных подтвердило указанные преимущества.

Фильтр блума, текстовый поиск

Короткий адрес: https://sciup.org/142178915

IDR: 142178915

Список литературы Псевдоматричный фильтр Блума для задач быстрого сравнения текстов

  • Knuth D., Morris Jr.J., Pratt V. Fast Pattern Matching in Strings//SIAM Journal on Computing. 1977. №6 (2). Р. 323-350.
  • Brin S., Davis J., García-Molina H. Copy detection mechanisms for digital documents//SIGMOD Rec. 1995. №24 (2). Р. 398-409.
  • Cormack G.V. Email Spam Filtering: A Systematic Review//Found. Trends Inf. Retr. 2008. №1 (4). Р. 335-455.
  • Butakov S., Scherbinin V. The toolbox for local and global plagiarism detection//Comput. Educ. 2009. №52 (4) Р. 781-788.
  • Bloom B.H. Space/time trade -offs in hash coding with allowable errors//Commun. ACM. 1970. №13 (7). Р. 422-426.
  • Федотов А.М., Барахнин В.Б. К вопросу о поиске документов «по аналогии»//Вестник Новосибирского государственного университета. Серия: Информационные технологии. 2009. Вып. 4. Т. 7. С. 5-7.
  • Псевдоматричный фильтр Блума для задач быстрого сравнения текстов
  • Bloom B.H.//Ibid.
  • Bloom B.H.//Ibid.
  • Broder A., Mitzenmacher M. Network Applications of Bloom Filters: A Survey//Internet Mathematics. 2005. №1 (4). P. 485-509.
  • Fan L., Cao P., Almeida J., Broder A. Summary cache: a scalable wide-area web cache sharing protocol. IEEE/ACM Trans. on Networking. 2000. №8 (3). Р. 281-293.
  • Guo D., Wu J., Chen H., Luo X. Theory and Network Applications of Dynamic Bloom Filters//INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings. 2006. Р. 1-12,
  • Karp R.M., Rabin M.O. Pattern-matching algorithms//IBM Journal of Research and Development. 1987. №31 (2). Р. 249-260.
  • Schleimer S., Wilkerson D., Aiken A. Winnowing: Local Algorithms for Document Fingerprinting//Proceedings of the ACM SIGMOD International Conference on Management of Data. 2003. P. 76-85.
  • Geravand S., Ahmadi M. A Novel Adjustable Matrix Bloom Filter-Based Copy Detection System for Digital Libraries//11th IEEE International Conference on Computer and Information Technology. CIT 2011. Proceedings. P. 518-525.
  • Geravand S., Ahmadi M.//Ibid.
  • Bloom B.H. Space/time trade-offs in hash coding with allowable errors//Commun. ACM. 1970. №13 (7). Р. 422-426.
  • Geravand S., Ahmadi M. A Novel Adjustable Matrix Bloom Filter-Based Copy Detection System for Digital Libraries//11th IEEE International Conference on Computer and Information Technology. CIT 2011. Proceedings. P. 518-525.
  • Potthast M., Eiselt A., Stein B., Barrón-Cedeño A., Rosso P. PAN Plagiarism Corpus PAN-PC-09.URL: http://www.uni-weimar.de/medien/webis/research/corpora.
  • Geravand S., Ahmadi M. A Novel Adjustable Matrix Bloom Filter-Based Copy Detection System for Digital Libraries//11th IEEE International Conference on Computer and Information Technology. CIT 2011. Proceedings. P. 518-525.
  • Schleimer S., Wilkerson D., Aiken A. Winnowing: Local Algorithms for Document Fingerprinting//Proceedings of the ACM SIGMOD International Conference on Management of Data. 2003. P. 76-85.
  • Schleimer S., Wilkerson D., Aiken A.//Ibid.
  • Stamatatos E. A survey of modern authorship attribution methods. J. Am. Soc. Inf. Sci. 2009. №60 (3). P. 538-556.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp