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

Общие вопросы программирования, алгоритмы и т.п.

Модератор: Модераторы

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

Сообщение azsx » 07.06.2017 03:56:44

У меня 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, не более половины количества слов.
Взял первые два элемента массива, сравнил их с следующими двумя элементами.
Если совпадение, то первые два элемента отбрасываю, выхожу из цикла.
Иначе продолжаю поиск в цикле, (беру три элемента массива и так далее до половины).
---
Алгоритм работы мне кажется жутко неэффективным, посоветуйте, пожалуйста, лучший вариант.
azsx
энтузиаст
 
Сообщения: 896
Зарегистрирован: 16.11.2015 06:38:32

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

Сообщение vitaly_l » 07.06.2017 07:41:34

azsx писал(а): посоветуйте, пожалуйста, лучший вариант.

Проверяйте на повторное вхождение слов, набранный массив - ещё на этапе разбития на слова.
И дайте мне уже гиперссылку на БД, пожалуйста.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3070
Зарегистрирован: 31.01.2012 16:41:41

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

Сообщение azsx » 07.06.2017 08:27:56

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

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

Уже ответил. Возможно данные нарушают какие нибудь авторские права, мне пока некогда об этом думать. Пока эти данные у меня -- это просто прикол, по вечерам читаю. Когда сделаю чат, подумаю об опен соурсе, узнаю про права.
azsx
энтузиаст
 
Сообщения: 896
Зарегистрирован: 16.11.2015 06:38:32

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

Сообщение Pavia » 07.06.2017 10:12:09

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

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

Сообщение azsx » 07.06.2017 11:12:35

Я бы делал так же. Но только не половину, а всего 6 слов

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

Сейчас проверяю орфографию, очень хочу за неделю управиться.
azsx
энтузиаст
 
Сообщения: 896
Зарегистрирован: 16.11.2015 06:38:32

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

Сообщение Pavia » 07.06.2017 11:50:39

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

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

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

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


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

Предложение это обычно не более 6 слов(сложно сочинённые это несколько предложений). Если слова повторяются более чем через 6 слов, то это уже повтор предложений. И их проверку можно сделать от точки или запятой или другого знака препинания.
Аватара пользователя
Pavia
постоялец
 
Сообщения: 172
Зарегистрирован: 07.01.2011 12:46:51

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

Сообщение azsx » 07.06.2017 12:27:14

Я пока тоже в начале пути.

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

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

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

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

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

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

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

Сообщение vitaly_l » 07.06.2017 13:04:36

Pavia писал(а):Думаю над тем где найти ещё штук 8 источников

сделаете лематизацию: http://www.solarix.ru/for_developers/ap ... -api.shtml
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3070
Зарегистрирован: 31.01.2012 16:41:41

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

Сообщение sts » 07.06.2017 13:06:20

а какова задача?
удалить повторы с сохранением остальной части строки? или игнорировать в дальнейших действиях?
sts
постоялец
 
Сообщения: 242
Зарегистрирован: 04.04.2008 12:15:44
Откуда: Тольятти

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

Сообщение azsx » 07.06.2017 15:20:16

удалить повторы с сохранением остальной части строки

Именно это, то есть вместо
с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
зы
Кстати, смотрю курс, умнею. То, что я называл сжатием слов и выделением корня -- это и есть лемматизация. Только для некоторых языков мне придётся стемминг делать (ну или не придётся, там видно будет).
Последний раз редактировалось azsx 07.06.2017 15:27:06, всего редактировалось 1 раз.
azsx
энтузиаст
 
Сообщения: 896
Зарегистрирован: 16.11.2015 06:38:32

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

Сообщение sts » 07.06.2017 15:25:04

понятно, если операция разовая то эффективность неважна, так сойдет.
а то я на фантазировал уже :) алгоритмов.
sts
постоялец
 
Сообщения: 242
Зарегистрирован: 04.04.2008 12:15:44
Откуда: Тольятти

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

Сообщение azsx » 07.06.2017 15:29:15

Операция не совсем разовая. Когда базу заполнять буду, там вообще все алгоритмы по обработке текста понадобятся. Так, что если не жутко сложно пишите или дайте ссылок и терминов.
azsx
энтузиаст
 
Сообщения: 896
Зарегистрирован: 16.11.2015 06:38:32

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

Сообщение vitaly_l » 07.06.2017 15:32:50

sts писал(а):если операция разовая то эффективность неважна, так сойдет

))))) +100500
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3070
Зарегистрирован: 31.01.2012 16:41:41


Вернуться в Общее

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5

Рейтинг@Mail.ru