Лингвофорум

Это радует, что на форуме столько математиков развелось. :)
Не знаю, к какому разделу математики относится моя задача, поэтому напишу здесь.

Итак, есть некоторое множество слов A, из него необходимо выделить минимальное подмножество B, которое максимально покрывает исходное множество A. Коэффициент покрытия множества равен отношению суммы коэффициентов покрытия всех его слов к количеству слов. Коэффициент покрытия слова равен отношению длины покрытой части слова ко всей длине слова. Часть слова считается покрытой, если она содержится хотя бы в одном слове множества B.
Пример. Множество A: лес, дрова, камень; множество B: лесоповал, камыш.
Покрытия слов:
лес — 1
дрова — 0,6
камень — 0,5
Покрытие множества A = 2,1/3 = 0,7

Накладываются ли ограничения на длину слов во множестве B?
Если мышь, а камыш то покрытие ξ=0?
Задачу, думаю, можно свести к поиску слогов^*. Множество слогов е минимальное множество "слов" которые покрывают остальные слова.

---

* Или односложных слов, также слоги надо бы включить во множество A.

Цитата: myst от марта 16, 2011, 10:48
Это радует, что на форуме столько математиков развелось. :)

Ну ведь матматика и лингвистика — друзья.

Цитата: hurufu от марта 16, 2011, 11:38
Накладываются ли ограничения на длину слов во множестве B?

Нет.

Цитата: hurufu от марта 16, 2011, 11:38
Если мышь, а камыш то покрытие ξ=0?

Почему? 0,75

Цитата: hurufu от марта 16, 2011, 11:38
Задачу, думаю, можно свести к поиску слогов.

Сомневаюсь.

Цитата: hurufu от марта 16, 2011, 11:38
Множество слогов е минимальное множество "слов" которые покрывают остальные слова.

Мне надо слова выделить, а не слоги. Да и со слогоделением в русском языке есть проблемы.

Цитата: hurufu от марта 16, 2011, 11:38
* Или односложных слов, также слоги надо бы включить во множество A.

Множество А — исходное множество слов. Оно не изменяемо в рамках задачи.

Стоило выделить в отдельную тему, и всё протухло. :'(

Ну для начала можно сделать брут-форсом: делаешь повермножество (як то по росыйску?), подсчитываешь значения для всех подмножеств. По ходу решения может чего-нибудь интересного выйти.

Входные данные — 18000 слов. Смекаешь? :)

Я в декабре пошёл по пути нечёткого сравнения, но потом нагрянули праздники, и... Ну ты понял.

Цитата: myst от марта 16, 2011, 14:51
Входные данные — 18000 слов. Смекаешь? :)

Да, гомновато.

По поводу брут форса, можно:

• упорядочить слова по длине
• каждое слово длины n накладывать на каждое слово длины n+1
• если слово длины n полностью накладывается на слово длины n+1, то удаляем из списка
• иначе повторяем пункт 2 для слов длины n+2
• ???
• что-то должно выйти

Цитата: myst от марта 16, 2011, 14:51
Входные данные — 18000 слов. Смекаешь? :)

Правда многовато слов для брут форса.

Цитата: RawonaM от марта 16, 2011, 15:09
Да, гомновато.

Цитата: hurufu от марта 16, 2011, 15:13
Правда многовато слов для брут форса.

Полный список — 69307. :)

Цитата: hurufu от марта 16, 2011, 15:13
По поводу брут форса, можно:
упорядочить слова по длине  каждое слово длины n накладывать на каждое слово длины n+1  если слово длины n полностью накладывается на слово длины n+1, то удаляем из списка  иначе повторяем пункт 2 для слов длины n+2  ???  что-то должно выйти

Это слишком грубо. Я использовал q-граммный нечёткий компаратор (http://staffwww.dcs.shef.ac.uk/people/S.Chapman/stringmetrics.html#qgram). На биграммах он выдаёт вполне релевантные коэффициенты подобия. Но для оценки покрытия он не годится. Хотя его алгоритм можно попробовать приспособить для нашей задачи...

Цитата: myst от марта 16, 2011, 15:47

Цитата: hurufu от марта 16, 2011, 15:13
По поводу брут форса, можно: ...

Это слишком грубо.

Грубая сила — груба́.

Цитата: myst от марта 16, 2011, 15:47
Я использовал q-граммный нечёткий компаратор (http://staffwww.dcs.shef.ac.uk/people/S.Chapman/stringmetrics.html#qgram).

Это когда слово «камыш» разбивается на «ка-ам-мы-ыш»?

Цитата: myst от марта 16, 2011, 15:47
Хотя его алгоритм можно попробовать приспособить для нашей задачи...

А мне кажется, это только ее усложнит :???.

Покрытие должно быть 100%?

Цитата: hurufu от марта 16, 2011, 20:01
Это когда слово «камыш» разбивается на «ка-ам-мы-ыш»?

Нет, это когда камыш разбивается на ка+ам+мы+ыш.

Цитата: hurufu от марта 16, 2011, 20:01
Покрытие должно быть 100%?

В идеале, да. Но размер множества B должен быть минимальным, поэтому несколькими процентами можно и пожертвовать, если это позволит заметно уменьшить мощность множества B.

Цитата: hurufu от марта 16, 2011, 20:01
А мне кажется, это только ее усложнит :???.

Почему усложнит? Там берётся пересечение множества n-грамм двух слов. А нам надо пересечение множества n-грамм слова из A и объединения множеств n-грамм всех слов из B. Коэффициент покрытия в этом случае равен отношению мощности пересечения к мощности множества n-грамм слова из A.

Цитата: myst от марта 16, 2011, 10:48
Итак, есть некоторое множество слов A, из него необходимо выделить минимальное подмножество (выделено мной. — К.) B, которое максимально покрывает исходное множество A.

Цитата: myst от марта 16, 2011, 10:48
Пример. Множество A: лес, дрова, камень; множество B: лесоповал, камыш.

Это как это?

Цитата: Квас от марта 16, 2011, 21:18
Это как это?

Этот пример иллюстрирует сущность покрытия, а не задачу.

Ну всё равно, раз  подмножество, то надо чтоб в примере было:
Множество A: лес, дрова, камень, лесоповал, камыш; множество B: лесоповал, камыш.

Коэффициенты покрытия суммируются по A? Если слово имеет две покрытые части, то они обе учитываются для коэффициента?

Цитата: Квас от марта 16, 2011, 21:28
Коэффициенты покрытия суммируются по A?

Не понял.

Цитата: Квас от марта 16, 2011, 21:28
Если слово имеет две покрытые части, то они обе учитываются для коэффициента?

Да. Совпадения отдельными буквами неинтересны, поэтому минимум биграммы.

Цитата: myst от марта 16, 2011, 21:31

Цитата: Квас от марта 16, 2011, 21:28
Коэффициенты покрытия суммируются по A?

Не понял.

Ну то есть для каждого слова из A вычисляем коэффициент покрытия словами из B, складываем все числа и делим на число элементов множества A? (В таком случае можно и не делить, потому что A фиксировано.)

Цитата: myst от марта 16, 2011, 10:48
Не знаю, к какому разделу математики относится моя задача, поэтому напишу здесь.

Дискретная математика, кстати.

Цитата: Квас от марта 16, 2011, 21:34
Дискретная математика, кстати.

Че-то у нас на дискретке ничего такого не видно.

Цитата: Квас от марта 16, 2011, 21:34
Ну то есть для каждого слова из A вычисляем коэффициент покрытия словами из B, складываем все числа и делим на число элементов множества A?

Да.

Цитата: Квас от марта 16, 2011, 21:34
Дискретная математика, кстати.

Да в ней чего только нет. Хотелось что-то более конкретное.

Цитата: RawonaM от марта 16, 2011, 21:39
Че-то у нас на дискретке ничего такого не видно.

Как говорил мой препод по дискретке: «Есть две математики: дискретная и непрерывная». Все задачи либо туда, либо сюда попадают. :)

Выходит, что максимальный коэффициент покрытия равен 1. Реализуется он, например, на любом подмножестве B, слова которого содержат все используемые буквы (это необходимое и достаточное условие, очевидно). Вопрос тогда в том, как можно уменьшить такое множество B.

Я же говорю, не меньше биграмм. Совпадения по отдельным буквам неинтересны. Забыл я про это сразу сказать. :(

Цитата: myst от марта 16, 2011, 21:41

ЦитироватьЧе-то у нас на дискретке ничего такого не видно.

Как говорил мой препод по дискретке: «Есть две математики: дискретная и непрерывная». Все задачи либо туда, либо сюда попадают. :)

Ну в целом правильно, наверное :) А на практике по-моему в дискретную математику чё хотят то и пихают, кроме анализа. :)

Цитата: RawonaM от марта 16, 2011, 21:58
А на практике по-моему в дискретную математику чё хотят то и пихают, кроме анализа. :)

Вот и я про что. :)