N-грамма: различия между версиями
Перейти к навигации
Перейти к поиску
w>Radixvinni~ruwiki (← Новая страница: «'''N-грамм''' определяется как последовательность из n элементов.<ref>Proceedings of the 7th Ann…») |
w>Radixvinni~ruwiki м |
||
| Строка 2: | Строка 2: | ||
== Использование N-грамм == | == Использование N-грамм == | ||
=== Общее использование N-грамм === | === Общее использование N-грамм === | ||
| − | N- | + | N-граммы в целом находят свое применение в широкой области наук. Они могут применяться, например, в области теоретической [[математика|математики]], [[биология|биологии]], [[картография|картографии]], а также в [[музыка|музыке]]. Наиболее часто использование N-грамм, включает следующие области:<ref>Wikipedia: N-Gram [online]. 22:47, 14 September 2004, 9 April 2009, at 05:14 . Доступно по адресу: <http://en.wikipedia.org/wiki/N-gram></ref> |
| − | * извлечение | + | * извлечение данных для кластеризации серии спутниковых снимков Земли из космоса, чтобы затем решить, какие конкретные части Земли на изображении, |
* поиск генетических последовательностей, | * поиск генетических последовательностей, | ||
| − | * в области [[генетика|генетики]] используются для определения того, | + | * в области [[генетика|генетики]] используются для определения того, с каких конкретных видов животных собраны образцы [[ДНК]], |
* в компьютерном [[сжатие данных|сжатии]], | * в компьютерном [[сжатие данных|сжатии]], | ||
| − | * с использованием N-грамм, как правило, | + | * с использованием N-грамм, как правило, индексированы данные, связанные со звуком. |
| + | Также N-граммы широко применяются в обработке естественного языка. | ||
=== Использование N-грамм для нужд обработки естественного языка === | === Использование N-грамм для нужд обработки естественного языка === | ||
| − | + | В области обработки естественного языка, N-граммы используется в основном для предугадывания на основе вероятностных моделей. N-граммная модель рассчитывает вероятность последнего слова N-грамма если известны все предыдущие. При использовании этого подхода для моделирования языка предполагается, что появление каждого слова зависит только от предыдущих слов.<ref>URAFSKY, Daniel, MARTIN, James H. Speech And Language Processing : An Introduction To Natural Language Processing, Computational Linguistics, And Speech Recognition. 2nd edition. Upper Saddle River: Prentice Hall, 2008. 1024 s. Доступно по адресу: <http://books.google.com/books?id=fZmj5UNK8AQC&dq=Speech+and+language+processing+:an+introduction+to+natural+language+processing&printsec=frontcover&source=bl&ots=LqS8_-HLQI&sig=0hNFclP0wlsKmjUtfyShEm437ws&hl=en&ei=sjrvSZaHCImI_QbE_cjDDw&sa=X&oi=book_result&ct=result&resnum=9>. ISBN 0-13-504196-1.</ref> | |
| − | В области обработки естественного языка, N- | ||
| − | Другое применение N- | + | Другое применение N-граммов является выявление [[плагиат]]а. Если разделить текст на несколько небольших фрагментов, представленных n-граммами, их легко сравнить друг с другом, и таким образом получить степень сходства контролируемых документов.<ref>Proceedings of the ITAT 2008, Information Technologies - Applications and Theory, Hrebienok, Slovakia, pp. 23-26, September 2008. ISBN 978-80-969184-8-5</ref> N-грамм, часто успешно используется для категоризации текста и языка. Кроме того, их можно использовать для создания функций, которые позволяют получать знания из текстовых данных. Используя N-грамм можно эффективно найти кандидатов, чтобы заменить слова с ошибками правописания.<ref>Wikipedia: N-Gram [online]. 22:47, 14 September 2004, 9 April 2009, at 05:14 . Доступно по адресу: <http://en.wikipedia.org/wiki/N-gram>.</ref> |
== Научно-исследовательские проекты Google == | == Научно-исследовательские проекты Google == | ||
| − | Исследовательские центры Google использовали N- | + | Исследовательские центры Google использовали N-граммные модели для широкого круга исследований и разработок. К ним относятся такие проекты, как статистический перевод с одного языка на другой, распознавание речи, исправление орфографических ошибок, извлечение информации и многое другое. Для целей этих проектов были использованы тексты корпусов, содержащих несколько триллионов слов. |
| − | Google решила создать свой учебный корпус. Проект называется Google teracorpus и он содержит 1 024 908 267 229 слов, собраных с общедоступных веб-сайтов.<ref>FRANZ, Alex, BRANTS, Thorsten. Official Google Research Blog : All Our N-gram are Belong to You [online]. Thursday, August 03, 2006 at 8/03/2006 11:26:00 AM. | + | Google решила создать свой учебный корпус. Проект называется Google teracorpus и он содержит 1 024 908 267 229 слов, собраных с общедоступных веб-сайтов.<ref>FRANZ, Alex, BRANTS, Thorsten. Official Google Research Blog : All Our N-gram are Belong to You [online]. Thursday, August 03, 2006 at 8/03/2006 11:26:00 AM. Доступно по адресу: <http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html>.</ref> |
== Методы для извлечения n-граммов == | == Методы для извлечения n-граммов == | ||
| − | В связи с частым использованием N- | + | В связи с частым использованием N-граммов для решения различных задач, необходим надежный и быстрый алгоритм для извлечения их из текста. Подходящий инструмент для извлечения n-граммов должен быть в состоянии работать с неограниченным размером текста, работать быстро и эффективно использовать имеющиеся ресурсы. Есть несколько методов извлечения N-граммов из текста. Эти методы основаны на разных принципах: |
| − | * ''Алгоритм Nagao 94''<ref>M. Nagao and S. Mori. A New Method of N-gram Statistics for Large Number of n and Automatic Extraction of Words and Phrases from Large Text Data of Japanese. In Proceedings of the 15th International Conference on Computational Linguistics (COLING 1994), Kyoto, Japan, 1994.</ref> | + | * ''Алгоритм Nagao 94'' для текстов на японском<ref>M. Nagao and S. Mori. A New Method of N-gram Statistics for Large Number of n and Automatic Extraction of Words and Phrases from Large Text Data of Japanese. In Proceedings of the 15th International Conference on Computational Linguistics (COLING 1994), Kyoto, Japan, 1994.</ref> |
| − | * ''Алгоритм Lempel-Ziv-Welch''<ref>Wikipedia : Lempel-Ziv-Welch [online]. 17:18, 8 October 2001, 26 April 2009, at 09:15 (UTC). | + | * ''Алгоритм Lempel-Ziv-Welch''<ref>Wikipedia : Lempel-Ziv-Welch [online]. 17:18, 8 October 2001, 26 April 2009, at 09:15 (UTC). Доступно по адресу: <http://en.wikipedia.org/wiki/Lempel-Ziv-Welch>.</ref> |
* ''Массив суффиксов'' | * ''Массив суффиксов'' | ||
* ''Дерево суффиксов'' | * ''Дерево суффиксов'' | ||
Версия от 20:22, 23 ноября 2012
N-грамм определяется как последовательность из n элементов.[1] С семантической точки зрения, это может быть последовательность звуков, слогов, слов или букв. На практике чаще встречается N-грамм как ряд слов. Последовательность из двух последовательных элементов часто называют биграммы, последовательность из трех элементов называется триграмма. Не менее четырех и выше элементов обозначаются как N-грамм, N заменяется на количество последовательных элементов.
Использование N-грамм
Общее использование N-грамм
N-граммы в целом находят свое применение в широкой области наук. Они могут применяться, например, в области теоретической математики, биологии, картографии, а также в музыке. Наиболее часто использование N-грамм, включает следующие области:[2]
- извлечение данных для кластеризации серии спутниковых снимков Земли из космоса, чтобы затем решить, какие конкретные части Земли на изображении,
- поиск генетических последовательностей,
- в области генетики используются для определения того, с каких конкретных видов животных собраны образцы ДНК,
- в компьютерном сжатии,
- с использованием N-грамм, как правило, индексированы данные, связанные со звуком.
Также N-граммы широко применяются в обработке естественного языка.
Использование N-грамм для нужд обработки естественного языка
В области обработки естественного языка, N-граммы используется в основном для предугадывания на основе вероятностных моделей. N-граммная модель рассчитывает вероятность последнего слова N-грамма если известны все предыдущие. При использовании этого подхода для моделирования языка предполагается, что появление каждого слова зависит только от предыдущих слов.[3]
Другое применение N-граммов является выявление плагиата. Если разделить текст на несколько небольших фрагментов, представленных n-граммами, их легко сравнить друг с другом, и таким образом получить степень сходства контролируемых документов.[4] N-грамм, часто успешно используется для категоризации текста и языка. Кроме того, их можно использовать для создания функций, которые позволяют получать знания из текстовых данных. Используя N-грамм можно эффективно найти кандидатов, чтобы заменить слова с ошибками правописания.[5]
Научно-исследовательские проекты Google
Исследовательские центры Google использовали N-граммные модели для широкого круга исследований и разработок. К ним относятся такие проекты, как статистический перевод с одного языка на другой, распознавание речи, исправление орфографических ошибок, извлечение информации и многое другое. Для целей этих проектов были использованы тексты корпусов, содержащих несколько триллионов слов.
Google решила создать свой учебный корпус. Проект называется Google teracorpus и он содержит 1 024 908 267 229 слов, собраных с общедоступных веб-сайтов.[6]
Методы для извлечения n-граммов
В связи с частым использованием N-граммов для решения различных задач, необходим надежный и быстрый алгоритм для извлечения их из текста. Подходящий инструмент для извлечения n-граммов должен быть в состоянии работать с неограниченным размером текста, работать быстро и эффективно использовать имеющиеся ресурсы. Есть несколько методов извлечения N-граммов из текста. Эти методы основаны на разных принципах:
- Алгоритм Nagao 94 для текстов на японском[7]
- Алгоритм Lempel-Ziv-Welch[8]
- Массив суффиксов
- Дерево суффиксов
- инвертированный индекс
Примечания
- ↑ Proceedings of the 7th Annual Conference ZNALOSTI 2008, Bratislava, Slovakia, pp. 54-65, February 2008. ISBN 978-80-227-2827-0.
- ↑ Wikipedia: N-Gram [online]. 22:47, 14 September 2004, 9 April 2009, at 05:14 . Доступно по адресу: <http://en.wikipedia.org/wiki/N-gram>
- ↑ URAFSKY, Daniel, MARTIN, James H. Speech And Language Processing : An Introduction To Natural Language Processing, Computational Linguistics, And Speech Recognition. 2nd edition. Upper Saddle River: Prentice Hall, 2008. 1024 s. Доступно по адресу: <http://books.google.com/books?id=fZmj5UNK8AQC&dq=Speech+and+language+processing+:an+introduction+to+natural+language+processing&printsec=frontcover&source=bl&ots=LqS8_-HLQI&sig=0hNFclP0wlsKmjUtfyShEm437ws&hl=en&ei=sjrvSZaHCImI_QbE_cjDDw&sa=X&oi=book_result&ct=result&resnum=9>. ISBN 0-13-504196-1.
- ↑ Proceedings of the ITAT 2008, Information Technologies - Applications and Theory, Hrebienok, Slovakia, pp. 23-26, September 2008. ISBN 978-80-969184-8-5
- ↑ Wikipedia: N-Gram [online]. 22:47, 14 September 2004, 9 April 2009, at 05:14 . Доступно по адресу: <http://en.wikipedia.org/wiki/N-gram>.
- ↑ FRANZ, Alex, BRANTS, Thorsten. Official Google Research Blog : All Our N-gram are Belong to You [online]. Thursday, August 03, 2006 at 8/03/2006 11:26:00 AM. Доступно по адресу: <http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html>.
- ↑ M. Nagao and S. Mori. A New Method of N-gram Statistics for Large Number of n and Automatic Extraction of Words and Phrases from Large Text Data of Japanese. In Proceedings of the 15th International Conference on Computational Linguistics (COLING 1994), Kyoto, Japan, 1994.
- ↑ Wikipedia : Lempel-Ziv-Welch [online]. 17:18, 8 October 2001, 26 April 2009, at 09:15 (UTC). Доступно по адресу: <http://en.wikipedia.org/wiki/Lempel-Ziv-Welch>.
См. также
ca:N-grama cs:N-gram de:N-Gramm en:N-gram es:N-grama eu:N-grama fi:N-grammi fr:N-gramme it:N-gramma mhr:N-грам