Страница 1 из 1

Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 03:56:44
azsx
У меня 3,4 млн строк в некоторых несколько первых строк повторяются дважды, то есть:
с1 с2 с3 с1 с2 с3 с4 с5 с6 с7 с8 с9
с1 с2 с3 с4 с5 с6
с1 с2 с1 с2 с3
Я думаю надо такой алгоритм:
---
делю строку на слова, загоняю слова в массив, количество слов делю надвое.
Цикл начинается с 2, не более половины количества слов.
Взял первые два элемента массива, сравнил их с следующими двумя элементами.
Если совпадение, то первые два элемента отбрасываю, выхожу из цикла.
Иначе продолжаю поиск в цикле, (беру три элемента массива и так далее до половины).
---
Алгоритм работы мне кажется жутко неэффективным, посоветуйте, пожалуйста, лучший вариант.

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 07:41:34
vitaly_l
azsx писал(а): посоветуйте, пожалуйста, лучший вариант.

Проверяйте на повторное вхождение слов, набранный массив - ещё на этапе разбития на слова.
И дайте мне уже гиперссылку на БД, пожалуйста.

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 08:27:56
azsx
Проверяйте на повторное вхождение слов, набранный массив - ещё на этапе разбития на слова.

Логично, делю размер массива на два, при заполнении. Если делиться нацело, то проверяю на совпадение. То есть в некоторых случаях придётся не весь массив заполнять по словам, а только до уровня, пока сопадений не нашёл. Спасибо.
Есть ещё способы?
И дайте мне уже гиперссылку на БД, пожалуйста.

Уже ответил. Возможно данные нарушают какие нибудь авторские права, мне пока некогда об этом думать. Пока эти данные у меня -- это просто прикол, по вечерам читаю. Когда сделаю чат, подумаю об опен соурсе, узнаю про права.

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 10:12:09
Pavia
Я бы делал так же. Но только не половину, а всего 6 слов. Итого перебор у вас будет не более 36.
Вам же всё равно такой проход делать один раз. - задача не параметрическая, оптимизировать нет смысла. А он константный и 3,6 миллиона он займёт не более 36 секунд. А скорее всего менее 1 секунды.

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 11:12:35
azsx
Я бы делал так же. Но только не половину, а всего 6 слов

В теории там может быть и 75 слов * 2 (то есть два раза повторяются по 75 слов).
Итого перебор у вас будет не более 36.

Сейчас проверяю орфографию, очень хочу за неделю управиться.

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 11:50:39
Pavia
Я пока тоже в начале пути. Только закончил оцифровку данных из тех что планировал. Думаю над тем где найти ещё штук 8 источников.

Я с СУБД не стал работать, решил что она медленная для моих задач. ДА и сейчас мои объёмы текстов всего 150 мб. С учётом того что в память я гружу не всё а только небольшие части. Эта работает очень быстро, правда оптимизацией я не занимался и таки 5 минут в энергосберегающем режиме. Предположу что мои 150 МБ это как 1 миллион ваших строк.

Орфография элементарно проверяется. Ищем все слова и которые встречаются менее заданного порога, те написаны с ошибкой.

Вы же после орфографии сделаете лематизацию и заведёте на каждое слово по номеру. Эта ускорит обработку в 6 раз, а то и более.


В теории там может быть и 75 слов * 2
Вы неправильно подходите. Нужно как в теории управления есть объект подал на него команду получил по обратной связи реакцию. По реакции подал вторую команду.
Другими словами вначале изучаете объект, а после на него воздействуете.
Вначале оцениваем сколько повторов на не большом кусочке, но вполне достаточном. Если для 1000 строк эта будет маленькая ошибка менее 1 процента то и на большой выборке ошибка будет менее 1 процента. Так что достаточно сделать оценку на 1000 или если хочется на 10 000 сток.

Предложение это обычно не более 6 слов(сложно сочинённые это несколько предложений). Если слова повторяются более чем через 6 слов, то это уже повтор предложений. И их проверку можно сделать от точки или запятой или другого знака препинания.

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 12:27:14
azsx
Я пока тоже в начале пути.

Может стоит объединиться, хотя бы в почте общаться? Вдвоём будет легче, потом может ещё кто подтянется.
---
Думаю над тем где найти ещё штук 8 источников.

А у вас какой (какие) источники?
Предположу что мои 150 МБ это как 1 миллион ваших строк.

Для первых 10 000 строк у меня длина не очищенной и не проверенной строки: вопрос: 245 и ответ 309 символов. Но база изменится кардинально.
Ищем все слова и которые встречаются менее заданного порога, те написаны с ошибкой.

Может Вы и правы, но у меня совсем ппц. Я сперва программой что смогу исправлю, а потом разбивать буду -- проверю Ваш способ.
Вы же после орфографии сделаете лематизацию и заведёте на каждое слово по номеру.

Не уверен, но попробую.
Другими словами вначале изучаете объект, а после на него воздействуете.

Именно здесь не согласен. Иногда проще обработать все строки, чем высказать какие то предположения и обрабатывать до какого то значения. К тому же в данной ситуации самая време затратная часть алгоритма -- это чтение строки с диска. Обработка на поиск дубликатов, наверное, будет занимать намного меньше времени. Я надеюсь.

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 13:04:36
vitaly_l
Pavia писал(а):Думаю над тем где найти ещё штук 8 источников

сделаете лематизацию: http://www.solarix.ru/for_developers/ap ... -api.shtml

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 13:06:20
sts
а какова задача?
удалить повторы с сохранением остальной части строки? или игнорировать в дальнейших действиях?

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 15:20:16
azsx
удалить повторы с сохранением остальной части строки

Именно это, то есть вместо
с1 с2 с3 с1 с2 с3 с4 с5 с6 с7 с8 с9
с1 с2 с3 с4 с5 с6
с1 с2 с1 с2 с3
записать в базу
с1 с2 с3 с4 с5 с6 с7 с8 с9
с1 с2 с3 с4 с5 с6
с1 с2 с3
зы
Кстати, смотрю курс, умнею. То, что я называл сжатием слов и выделением корня -- это и есть лемматизация. Только для некоторых языков мне придётся стемминг делать (ну или не придётся, там видно будет).

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 15:25:04
sts
понятно, если операция разовая то эффективность неважна, так сойдет.
а то я на фантазировал уже :) алгоритмов.

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 15:29:15
azsx
Операция не совсем разовая. Когда базу заполнять буду, там вообще все алгоритмы по обработке текста понадобятся. Так, что если не жутко сложно пишите или дайте ссылок и терминов.

Re: Алгоритм поиска повторов в начале строки

СообщениеДобавлено: 07.06.2017 15:32:50
vitaly_l
sts писал(а):если операция разовая то эффективность неважна, так сойдет

))))) +100500