Здравствуйте, 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>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, tarkil, Вы писали:
T>Завести словарь окончаний и суффиксов с признаком, обязательно ли это окончание в самом конце ("ся") или нет (прочие). Пока на конце слова символы, входящие в словарь, откусываем их в окончание. То, что останется, назовём основой. Слишком короткие суффиксы (типа "и") имеет смысл заносить в словарь не отдельной строкой, а объединять с другими, с которыми они могут использоваться (и фиг с ним, что сочетаний очень много будет, зато быстрее и надёжней).
Прикол в том, что ты можешь откусить значимый конец посчитав его незначимым.
Например слово пилилка:
отбрасываем ка -- как суффикс+окончание
отбрасываем ил -- как стандартный суффикс
отбрасываем ил -- как стандартный суффикс
остается п
Таких слов хватает. У меня такое подозрение что есть слова которые можно представить в виде совокупности одних окончаний и суффиксов.
Вот тебе один из подводных камней. Далеко не единственный.
Далее слово ПРИМА начинается на стандартную приставку при, тем не менее ее удалять нельзя.
А впрочем, ты меня почти убедил.
T>Допускаю (но не очень верю), не пробовал. Просто излагаю, куда бы стал двигаться я, стой передо мной такая задача.
Задачи то как таковой не стоит
Если уважаемый господин Аноним поставит конкретное условие и конкретные задачи, можно будет продолжить разговор.
T>Punto Switcher весьма качественно делает перекодировку туда и обратно (якшизилось жмурчало подъездно-угловастенькое -> yakshizilos' zhmurchalo pod'ezdno-uglovasten'koe -> якшизилосъ жмурчало подъездно-угловастенъкое). Кто мешает применить этот алгоритм?
Твоя права.
T>P.S. Да, ещё вспомнил про один интересный материальчик — MetaPhoneRu, там стояла сходная задача — искать похожие фамилии.
Не смотрел, может потом.
Здравствуйте, Аноним, Вы писали:
А>Stroka1 ="А.пугачёва — Балалайка" \ А>Stroka1 ="Пугачёва-балалайка" / здесь примерно 98-99% (Вот как раз надо и подсчитать!)
А что будешь делать с этим: "Pugacheva — Balalayka"?
Забей, то что ты хочешь для тебя нереально.
Здравствуйте, tarkil, Вы писали:
T>при-страст-ился
T>"при" — типичная приставка, подбирается из словаря, "ил" и "ся" — окончания, оттуда же, то, что осталось — считаем корнем.
Вот о таких я и писал.
Можешь взять книжку по русскому языку и ознакомиться поближе.
при — приставка
страст — корень
и — первый суффикс
л — второй суффикс
ся — постфикс
Кстати с выделением корня тоже огромные проблемы.
корень слова бриться — бр.
если искать его в слове, то можеть получиться что слово бригада — имеет два корня (бр и гад)
(брей гада ! )
Здравствуйте, tinytjan, Вы писали:
T>Вот о таких я и писал.
По русскому языку — пять. Молодец, можешь садиться.
Только для целей выяснения похожести строк делить хвост слова на суффиксы разных видов и окончания тоже разных видов совершенно бессмысленно. В словах с двумя корнями выделять оба тоже nafique не нужно, как и связку между ними. Важна идея — середина слова самая важная, префикс тоже существенен (фактически, его можно и не выделять, ограничившись окончаниями-суффиксами), а окончания — маловажны.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, IIIypuk, Вы писали:
III>>При моей реализации подсчета вектора корреляции вот твкая херня выходит! III>>Это для первого варианта где 1 это несовпадение с твоим Sinclair S>Я мог ошибиться. Вот код:
Я тут сам не моного прогнал,сам уже разобрался!
Кому интересно вот как я нахожу %;
x=vect_cor(str1,str1);
y=vect_cor(str2,str2);
z=vect_cor(str1,str2);
Привет народ!
Подскажите пожалуйста
Как сравнить две строки и получить их %- соотнощение,есть ли готовые какие нибудь решения или подскажите какими алгоритмами можно воспользоваться
Например 1:
Stroka1 ="ABCDEF"; \
Stroka2 ="BEFCAD"; / % соотношение этих строк 100% (Здесь строки одинаковы просто переставленны местами символы!)
Например 2:
Stroka1 ="А.пугачёва — Балалайка" \
Stroka1 ="Пугачёва-балалайка" / здесь примерно 98-99% (Вот как раз надо и подсчитать!)
Примерно вот как хочется реализовать % соотнощение строк, только незнаю как!
И не обязательно, что строки будут одинаковые по длинне.Я так думаю что надо сравнивать как-то по символьно эти строки,а не искать подстроку в строке!
А может я ошибаюсь! Я буду очень благодарен за любую помощь в этом направлении!
А так же подскажите как прочитать Тэги ID3v1 и ID3v2 из MP3-хи!!!(на си)
Здравствуйте, Аноним, Вы писали:
А>Привет народ! А>Подскажите пожалуйста А>Как сравнить две строки и получить их %- соотнощение,есть ли готовые какие нибудь решения или подскажите какими алгоритмами можно воспользоваться
Все просто.
Берешь символ. Проверяешь сколько раз он входит в каждую из строк. Находишь разницу для двух строк. Суммируешь модули этих разниц для всех символов. Делишь сумму на длину строки и получаешь процент.
Здравствуйте, tinytjan, Вы писали:
T>Берешь символ. Проверяешь сколько раз он входит в каждую из строк. Находишь разницу для двух строк. Суммируешь модули этих разниц для всех символов. Делишь сумму на длину строки и получаешь процент.
Т.е. "Портос" и "стопор" это 100%-но эквивалентные слова?
Я бы копал в сторону разбиения на слова, выделение (по какому-нибудь простому алгоритму) приставки, корня, окончания. Включая в окончание и суффиксы. Потом перебирать слова каждой из строк и искать похожие в строке-оппоненте. Похожесть определяется через вычисление дистанции для приставки-корня-окончания отдельно и свёртывания с весами в одну величину. Корень имеет максимальный вес, приставка — поменьше, окончание — самый маленький.
Что касается самого алгоритма дистанции...
Можно поискать алгоритмы на тему "как сделать из мухи слона" или "сколько нужно операций, чтобы из слова A сделать слово B". Кол-во операций и будет дистанцией. Глянь здесь, вроде оно.
А насчет корней, суффиксов и т.д. явный загон.
Половина русских это сделать не могут, а ты это запрограмить предлагаешь.
Попробуй разложить слово "пристрастился" или что-нить подобное. В этом слове окончания вообще нет если я правильно помню.
Здравствуйте, tinytjan, Вы писали:
T>А насчет корней, суффиксов и т.д. явный загон. T>Попробуй разложить слово "пристрастился" или что-нить подобное. В этом слове окончания вообще нет если я правильно помню.
при-страст-ился
"при" — типичная приставка, подбирается из словаря, "ил" и "ся" — окончания, оттуда же, то, что осталось — считаем корнем.
Здравствуйте, 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, там стояла сходная задача — искать похожие фамилии.
Здравствуйте, 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 разных файла!!!
Вот и хочу чтоб подсказали, как это все реализовать, а раскладывание слов на приставки,корни и т.д. — этот вариант отпадает!
Это можно е..я все эти исключения вручную вводить,и анализировать какие еще могут быть вариации !
Может брать слова от разделителя до разделителя (точки,тире,пробелы и т.д.) и сравнивать их уже или искать в другой строке???
Здравствуйте, Sinclair, Вы писали:
S>Попробуй посчитать вектор корреляции. Вектор устроен так: S>идешь вдоль обеих строк и для каждого совпадения инкрементируешь счетчик. Полученное значение записываешь в нулевую позицию вектора. S>Затем сдвигаешь одну строку относительно другой на один символ и снова считаешь количество совпадений. Для твоего примера получится вот так: S>
S>Максимумы указывают на то, что есть два похожих фрагмента, расположенных по-разному. S>Ну ладно, это все детали. А смысл — в том, что похожесть можно определить, вычисляя "длину" этого вектора. Для длины можно много всяких мер ввести. Вот, к примеру, простейшая мера — сумма компонентов поделить на количество элементов. Для твоего примера получится 2.56, для моего — 2.69. Для балалайки — 2.13. S>При этом бутусов будет похож на балалайку только на 0.42. S>Так что это число может служить мерой похожести.
Кстати прикольный метод Мне нравиться
Эсли не трудно можешь код самого вектора запостить или скнуть на мыло mailto:kf-121@list.ru
Здравствуйте, wildwind, Вы писали:
W>Здравствуйте, Аноним, Вы писали:
А>>Stroka1 ="А.пугачёва — Балалайка" \ А>>Stroka1 ="Пугачёва-балалайка" / здесь примерно 98-99% (Вот как раз надо и подсчитать!)
W>А что будешь делать с этим: "Pugacheva — Balalayka"? W>Забей, то что ты хочешь для тебя нереально.
Пусть пытается. В этом мире становятся известными только те, кто делает невозможное.
[ Posted via RSDN@Home 1.1.4 beta 4 (303) listening to silent ]
It's kind of fun to do the impossible (Walt Disney)
Здравствуйте, IIIypuk, Вы писали:
III>При моей реализации подсчета вектора корреляции вот твкая херня выходит! III>Это для первого варианта где 1 это несовпадение с твоим Sinclair
Я мог ошибиться. Вот код:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Math;
type
TForm1 = class(TForm)
Edit1: TEdit;
Edit2: TEdit;
Button1: TButton;
Memo1: TMemo;
Label1: TLabel;
procedure Button1Click(Sender: TObject);
private{ Private declarations }public{ Public declarations }end;
var
Form1: TForm1;
implementation{$R *.dfm}function ArrayToString(const a: array of integer): string; forward;
function VectorLength(const a: array of integer): extended;
var
R2: extended;
i: integer;
begin
R2:= 0;
for i:= Low(a) to High(a) do
R2:= R2 + a[i];
Result := R2/((High(a)+1));
end;
procedure TForm1.Button1Click(Sender: TObject);
var
N, K: integer;
str1, str2, str3: string;
i, j: integer;
Match: array of Integer;
begin
str1:= Edit1.Text;
str2:= Edit2.Text;
N:= max(Length(str1), Length(str2));
if Length(str2)<N
then begin
str3:= str2;
str2:= str1;
str1:= str3;
end;
SetLength(Match, N);
for i:=0 to N-1 do
begin
K:= 0;
for j:= 0 to Length(str1)-1 do
if str1[j+1] = str2[(j+i) mod N + 1]
then Inc(K);
Match[i]:= K;
end;
Memo1.Lines.Text:= ArrayToString(Match);
Label1.Caption := FloatToStr(VectorLength(Match));
end;
function ArrayToString(const a: array of integer): string;
var
i: integer;
begin
for i:= Low(a) to High(a) do
Result:= Result+IntToStr(a[i])+', ';
if (Length(Result)>0) then SetLength(Result, Length(Result)-2);
end;
end.
... << RSDN@Home 1.1.4 beta 5 rev. 395>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали: S>Попробуй посчитать вектор корреляции.
— Единственно правильное тут предложение. Да, посчитать корреляцией можно. Можно и другими методами, например параметрической корреляцией или хешированием строк, главное выбрать корректную метрику.
Вместо того чтобы тратить время на объяснения, просто
а) найти искомое легко можно зная точные слова поиска. Эти ключевые слова "нечеткое сравнение" и "мягкое сравнение". fuzzy string compare, fuzzy comparison algorithms, soft string comparison.
б) выложу у себя рабочие исходники нечеткого сравнения строк вместе в документацией
Здравствуйте, <Аноним>, Вы писали:
А>Привет народ! А>Подскажите пожалуйста
А>А так же подскажите как прочитать Тэги ID3v1 и ID3v2 из MP3-хи!!!(на си) Формат MP3. А дальше — только прямые руки и кривые извилины (главное — не перепутать)
А>Зарание большое спасибо!!!
Здравствуйте, Kaa, Вы писали:
Н>>Судя по обсуждению (ну в частности то, что будут строки типа "дущие домой" и "идущие дамой") можно глянуть на SoundEx.
Kaa>А есть SoundEx для русского языка?
Здравствуйте, Dimonka, Вы писали:
D>А есть ли простые алгоритмы посчитать похожесть строк без учёта перестановок слов?
D>Допустим, различие двух строк только в пробелах, запятых или сокращениях слов.
Похожесть по whitespace и пунктуации считается элементарно с помошью разбиения строки на лексемы. Последовательность такая:
— берем список разделителей (пунктуация + whitespace);
— находим в строке все слова (слово — последовательность символов между разделителями).
— строим топ слов (по частоте)
— сравниваем 2 получаенных топа.
Собственно, проценты — мера, полученная от оцифровывания "пересечения" двух полученных последовательностей.
Проблема у этого алгоритма — перестановки одних и тех же слов составляют эквивалентные последовательности.
Для определения похожести также и по содержимому (т.е. с учетом взаимного расположения слов) можно использовать шинглы/супершинглы. Механизм это медленный, но верный. Он, правда, не прадназначен для вычисления близости, а может быть использован именно для поиска похожих. Вроде, это то, что требовалось изначально.
Также можно медитировать по поводу функции Левенштейна (особенно, если ее применить не к символам строки, а к выделенным словам).
Здравствуйте, Kaa, Вы писали:
Kaa>- берем список разделителей (пунктуация + whitespace); Kaa>- находим в строке все слова (слово — последовательность символов между разделителями). Kaa>- строим топ слов (по частоте) Kaa>- сравниваем 2 получаенных топа.
Мне кажется здесь можно поступить как-то проще.. Например выделить словарь обоих строк и сделать цепочку из индексов слов по словарю для каждой строки. Единственное, что смущает, это как сравнивать эти цепочки и как выявлять сокращённые слова (или, например, слова с ошибками или с несколько разной транслитерацией букв)
Kaa>Собственно, проценты — мера, полученная от оцифровывания "пересечения" двух полученных последовательностей.
Kaa>Проблема у этого алгоритма — перестановки одних и тех же слов составляют эквивалентные последовательности.
!
