Привет народ!
Подскажите пожалуйста
Как сравнить две строки и получить их %- соотнощение,есть ли готовые какие нибудь решения или подскажите какими алгоритмами можно воспользоваться
Например 1:
Stroka1 ="ABCDEF"; \
Stroka2 ="BEFCAD"; / % соотношение этих строк 100% (Здесь строки одинаковы просто переставленны местами символы!)
Например 2:
Stroka1 ="А.пугачёва — Балалайка" \
Stroka1 ="Пугачёва-балалайка" / здесь примерно 98-99% (Вот как раз надо и подсчитать!)
Примерно вот как хочется реализовать % соотнощение строк, только незнаю как!
И не обязательно, что строки будут одинаковые по длинне.Я так думаю что надо сравнивать как-то по символьно эти строки,а не искать подстроку в строке!
А может я ошибаюсь! Я буду очень благодарен за любую помощь в этом направлении!
А так же подскажите как прочитать Тэги ID3v1 и ID3v2 из MP3-хи!!!(на си)
Здравствуйте, Аноним, Вы писали:
А>Привет народ! А>Подскажите пожалуйста А>Как сравнить две строки и получить их %- соотнощение,есть ли готовые какие нибудь решения или подскажите какими алгоритмами можно воспользоваться
Все просто.
Берешь символ. Проверяешь сколько раз он входит в каждую из строк. Находишь разницу для двух строк. Суммируешь модули этих разниц для всех символов. Делишь сумму на длину строки и получаешь процент.
Здравствуйте, Аноним, Вы писали:
А>Stroka1 ="А.пугачёва — Балалайка" \ А>Stroka1 ="Пугачёва-балалайка" / здесь примерно 98-99% (Вот как раз надо и подсчитать!)
А что будешь делать с этим: "Pugacheva — Balalayka"?
Забей, то что ты хочешь для тебя нереально.
Здравствуйте, tinytjan, Вы писали:
T>Берешь символ. Проверяешь сколько раз он входит в каждую из строк. Находишь разницу для двух строк. Суммируешь модули этих разниц для всех символов. Делишь сумму на длину строки и получаешь процент.
Т.е. "Портос" и "стопор" это 100%-но эквивалентные слова?
Я бы копал в сторону разбиения на слова, выделение (по какому-нибудь простому алгоритму) приставки, корня, окончания. Включая в окончание и суффиксы. Потом перебирать слова каждой из строк и искать похожие в строке-оппоненте. Похожесть определяется через вычисление дистанции для приставки-корня-окончания отдельно и свёртывания с весами в одну величину. Корень имеет максимальный вес, приставка — поменьше, окончание — самый маленький.
Что касается самого алгоритма дистанции...
Можно поискать алгоритмы на тему "как сделать из мухи слона" или "сколько нужно операций, чтобы из слова A сделать слово B". Кол-во операций и будет дистанцией. Глянь здесь, вроде оно.
А насчет корней, суффиксов и т.д. явный загон.
Половина русских это сделать не могут, а ты это запрограмить предлагаешь.
Попробуй разложить слово "пристрастился" или что-нить подобное. В этом слове окончания вообще нет если я правильно помню.
Здравствуйте, tinytjan, Вы писали:
T>А насчет корней, суффиксов и т.д. явный загон. T>Попробуй разложить слово "пристрастился" или что-нить подобное. В этом слове окончания вообще нет если я правильно помню.
при-страст-ился
"при" — типичная приставка, подбирается из словаря, "ил" и "ся" — окончания, оттуда же, то, что осталось — считаем корнем.
Здравствуйте, tarkil, Вы писали:
T>при-страст-ился
T>"при" — типичная приставка, подбирается из словаря, "ил" и "ся" — окончания, оттуда же, то, что осталось — считаем корнем.
Вот о таких я и писал.
Можешь взять книжку по русскому языку и ознакомиться поближе.
при — приставка
страст — корень
и — первый суффикс
л — второй суффикс
ся — постфикс
Кстати с выделением корня тоже огромные проблемы.
корень слова бриться — бр.
если искать его в слове, то можеть получиться что слово бригада — имеет два корня (бр и гад)
(брей гада ! )
Здравствуйте, tinytjan, Вы писали:
T>Вот о таких я и писал.
По русскому языку — пять. Молодец, можешь садиться.
Только для целей выяснения похожести строк делить хвост слова на суффиксы разных видов и окончания тоже разных видов совершенно бессмысленно. В словах с двумя корнями выделять оба тоже nafique не нужно, как и связку между ними. Важна идея — середина слова самая важная, префикс тоже существенен (фактически, его можно и не выделять, ограничившись окончаниями-суффиксами), а окончания — маловажны.
Здравствуйте, tarkil, Вы писали:
T>Только для целей выяснения похожести строк делить хвост слова на суффиксы разных видов и окончания тоже разных видов совершенно бессмысленно. В словах с двумя корнями выделять оба тоже nafique не нужно, как и связку между ними. Важна идея — середина слова самая важная, префикс тоже существенен (фактически, его можно и не выделять, ограничившись окончаниями-суффиксами), а окончания — маловажны.
Я веду к тому, что формализовать представление слов в русском языке таким макаром задачка далеко не тривиальная.
Как ты определишь похожесть слов класть и положил ?
Разложение на составные части слов -- бесперспективное (по количеству затраченного времени и нервных клеток) и очень трудоемкое занятие. Впрочем, я могу быть неправ. Поправьте меня если ошибаюсь.
В этой задаче будет столько подводных камней, что заколебется о них спотыкаться.
Максимум -- проверять сочетания символов.
А как сопоставлять похожие названия на русском и транслите -- я вообще не представляю.
Так что предложенное мной решение имеет смысл и имеет место быть.
Здравствуйте, Аноним, Вы писали:
А>Привет народ! А>Подскажите пожалуйста А>Как сравнить две строки и получить их %- соотнощение,есть ли готовые какие нибудь решения или подскажите какими алгоритмами можно воспользоваться
А>Например 1: А>Stroka1 ="ABCDEF"; \ А>Stroka2 ="BEFCAD"; / % соотношение этих строк 100% (Здесь строки одинаковы просто переставленны местами символы!)
А>Например 2: А>Stroka1 ="А.пугачёва — Балалайка" \ А>Stroka1 ="Пугачёва-балалайка" / здесь примерно 98-99% (Вот как раз надо и подсчитать!)
Похоже ты сам не знаешь, чего хочешь.
Я бы попробовал вычислять расстояние между первой строкой и всеми вариантами второй (циклически сдвинутыми), потом выбрать минимальное.
Здравствуйте, tinytjan, Вы писали:
T>Я веду к тому, что формализовать представление слов в русском языке таким макаром задачка далеко не тривиальная. T>Как ты определишь похожесть слов класть и положил ?
Увы. На это придётся забить в первом приближении, очень сложно. Но — такие пары нужно запоминать в качестве тестовых примеров для алгоритма, чтоб он пусть не 90% дал, но хотя бы 50%.
T>Разложение на составные части слов -- бесперспективное (по количеству затраченного времени и нервных клеток) и очень трудоемкое занятие. Впрочем, я могу быть неправ. Поправьте меня если ошибаюсь.
Завести словарь окончаний и суффиксов с признаком, обязательно ли это окончание в самом конце ("ся") или нет (прочие). Пока на конце слова символы, входящие в словарь, откусываем их в окончание. То, что останется, назовём основой. Слишком короткие суффиксы (типа "и") имеет смысл заносить в словарь не отдельной строкой, а объединять с другими, с которыми они могут использоваться (и фиг с ним, что сочетаний очень много будет, зато быстрее и надёжней).
Ну и много-много тестовых слов всяких разных экзотических видов, на которых вручную проверим корректность разложения.
T>В этой задаче будет столько подводных камней, что заколебется о них спотыкаться.
Допускаю (но не очень верю), не пробовал. Просто излагаю, куда бы стал двигаться я, стой передо мной такая задача.
T>А как сопоставлять похожие названия на русском и транслите -- я вообще не представляю.
Punto Switcher весьма качественно делает перекодировку туда и обратно (якшизилось жмурчало подъездно-угловастенькое -> yakshizilos' zhmurchalo pod'ezdno-uglovasten'koe -> якшизилосъ жмурчало подъездно-угловастенъкое). Кто мешает применить этот алгоритм?
T>Так что предложенное мной решение имеет смысл и имеет место быть.
Sure. Только у него ложных похожестей больше будет ловиться.
P.S. Да, ещё вспомнил про один интересный материальчик — MetaPhoneRu, там стояла сходная задача — искать похожие фамилии.
Здравствуйте, tarkil, Вы писали:
T>Завести словарь окончаний и суффиксов с признаком, обязательно ли это окончание в самом конце ("ся") или нет (прочие). Пока на конце слова символы, входящие в словарь, откусываем их в окончание. То, что останется, назовём основой. Слишком короткие суффиксы (типа "и") имеет смысл заносить в словарь не отдельной строкой, а объединять с другими, с которыми они могут использоваться (и фиг с ним, что сочетаний очень много будет, зато быстрее и надёжней).
Прикол в том, что ты можешь откусить значимый конец посчитав его незначимым.
Например слово пилилка:
отбрасываем ка -- как суффикс+окончание
отбрасываем ил -- как стандартный суффикс
отбрасываем ил -- как стандартный суффикс
остается п
Таких слов хватает. У меня такое подозрение что есть слова которые можно представить в виде совокупности одних окончаний и суффиксов.
Вот тебе один из подводных камней. Далеко не единственный.
Далее слово ПРИМА начинается на стандартную приставку при, тем не менее ее удалять нельзя.
А впрочем, ты меня почти убедил.
T>Допускаю (но не очень верю), не пробовал. Просто излагаю, куда бы стал двигаться я, стой передо мной такая задача.
Задачи то как таковой не стоит
Если уважаемый господин Аноним поставит конкретное условие и конкретные задачи, можно будет продолжить разговор.
T>Punto Switcher весьма качественно делает перекодировку туда и обратно (якшизилось жмурчало подъездно-угловастенькое -> yakshizilos' zhmurchalo pod'ezdno-uglovasten'koe -> якшизилосъ жмурчало подъездно-угловастенъкое). Кто мешает применить этот алгоритм?
Твоя права.
T>P.S. Да, ещё вспомнил про один интересный материальчик — MetaPhoneRu, там стояла сходная задача — искать похожие фамилии.
Не смотрел, может потом.
Здравствуйте, tinytjan, Вы писали:
T>Прикол в том, что ты можешь откусить значимый конец посчитав его незначимым. T>Например слово пилилка:
Да, я помню про это. Вопрос, как обычно, стоит в том, много ли таких слов. Если мало, можно и пренебречь, если много — думать дальше. Я уже просто не буду проводить анализ — трудоёмко, а задача всё ж не передо мной стоит.
T>Если уважаемый господин Аноним поставит конкретное условие и конкретные задачи, можно будет продолжить разговор.
Здравствуйте, Аноним, Вы писали:
А>Привет народ! А>Подскажите пожалуйста А>Как сравнить две строки и получить их %- соотнощение,есть ли готовые какие нибудь решения или подскажите какими алгоритмами можно воспользоваться
А>Например 1: А>Stroka1 ="ABCDEF"; \ А>Stroka2 ="BEFCAD"; / % соотношение этих строк 100% (Здесь строки одинаковы просто переставленны местами символы!)
А>Например 2: А>Stroka1 ="А.пугачёва — Балалайка" \ А>Stroka1 ="Пугачёва-балалайка" / здесь примерно 98-99% (Вот как раз надо и подсчитать!)
А>Примерно вот как хочется реализовать % соотнощение строк, только незнаю как! А>И не обязательно, что строки будут одинаковые по длинне.Я так думаю что надо сравнивать как-то по символьно эти строки,а не искать подстроку в строке! А>А может я ошибаюсь! Я буду очень благодарен за любую помощь в этом направлении!
А>А так же подскажите как прочитать Тэги ID3v1 и ID3v2 из MP3-хи!!!(на си)
А>Зарание большое спасибо!!!
Вообщем то это все для поиска одинаковой музыки,посредствам сравнивания их имен файлов.
Имя имеет вид Артист-Название или Артист — Название, короче с разными разделителями.
вот еще пример
В. бутусов и ю-питер — Песня идущего домой (dj skydreamer remix).mp3
В. бутусов и ю-питер — Песня идущево домой (remix).mp3
в большенствеслечает разделитель "пробел-пробел"
Может разница всего тобыть в одной букве,а машина знает что это 2 разных файла!!!
Вот и хочу чтоб подсказали, как это все реализовать, а раскладывание слов на приставки,корни и т.д. — этот вариант отпадает!
Это можно е..я все эти исключения вручную вводить,и анализировать какие еще могут быть вариации !
Может брать слова от разделителя до разделителя (точки,тире,пробелы и т.д.) и сравнивать их уже или искать в другой строке???
Здравствуйте, IIIypuk, Вы писали:
III>Вообщем то это все для поиска одинаковой музыки,посредствам сравнивания их имен файлов. III>Имя имеет вид Артист-Название или Артист — Название, короче с разными разделителями. III>вот еще пример III>В. бутусов и ю-питер — Песня идущего домой (dj skydreamer remix).mp3 III>В. бутусов и ю-питер — Песня идущево домой (remix).mp3
Попробуй посчитать вектор корреляции. Вектор устроен так:
идешь вдоль обеих строк и для каждого совпадения инкрементируешь счетчик. Полученное значение записываешь в нулевую позицию вектора.
Затем сдвигаешь одну строку относительно другой на один символ и снова считаешь количество совпадений. Для твоего примера получится вот так:
Максимумы указывают на то, что есть два похожих фрагмента, расположенных по-разному.
Ну ладно, это все детали. А смысл — в том, что похожесть можно определить, вычисляя "длину" этого вектора. Для длины можно много всяких мер ввести. Вот, к примеру, простейшая мера — сумма компонентов поделить на количество элементов. Для твоего примера получится 2.56, для моего — 2.69. Для балалайки — 2.13.
При этом бутусов будет похож на балалайку только на 0.42.
Так что это число может служить мерой похожести.
... << RSDN@Home 1.1.4 beta 4 rev. 347>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Попробуй посчитать вектор корреляции. Вектор устроен так: S>идешь вдоль обеих строк и для каждого совпадения инкрементируешь счетчик. Полученное значение записываешь в нулевую позицию вектора. S>Затем сдвигаешь одну строку относительно другой на один символ и снова считаешь количество совпадений. Для твоего примера получится вот так: S>
S>Максимумы указывают на то, что есть два похожих фрагмента, расположенных по-разному. S>Ну ладно, это все детали. А смысл — в том, что похожесть можно определить, вычисляя "длину" этого вектора. Для длины можно много всяких мер ввести. Вот, к примеру, простейшая мера — сумма компонентов поделить на количество элементов. Для твоего примера получится 2.56, для моего — 2.69. Для балалайки — 2.13. S>При этом бутусов будет похож на балалайку только на 0.42. S>Так что это число может служить мерой похожести.
Кстати прикольный метод Мне нравиться
Эсли не трудно можешь код самого вектора запостить или скнуть на мыло mailto:kf-121@list.ru
)
!
