Есть задача. Дана строка состоящая из разного набора слов. Пример: "метан, чугун, вода, земля, воздух, дерево".
Набор слов может быть любой. Их обычно всегда не более 10.

Есть несколько наборов слов:

Первый набор слов:
вода
земля
космос
...

Второй набор слов:
сайт,
компьютер
интернет
pc
принтер
...

Третий набор слов:
девушка
парень
приятель
друг
...

Четвертый набор слов(АНТИ-набор):
xxx
xxx
xxx
....


Всего имеется 4 набора слов. Каждый из которых состоит в из 10-50 слов. Слова разделены заданным символом между собой.

Мне нужно сделать функцию, которая бы получала на входе строку для анализа, типа: "метан, чугун, вода, земля, воздух, дерево", 4 группы ключевых слов и возвращала бы TRUE или FALSE.


TRUE возвращается, когда выполняются ВСЕ 4 условия:

1. Хотя бы одно слово из ПЕРВОГО набора слов присутствует в строке для анализа.
2. Хотя бы одно слово из ВТОРОГО набора слов присутствует в строке для анализа.
3. Хотя бы одно слово из ТРЕТЬЕГО набора слов присутствует в строке для анализа.

4. Ни одно из слов ЧЕТВЕРТОГО набора слов НЕ присутствует в строке для анализа.

Очень важное дополнение: Если в каком-либо наборе слов вообще нет слов, то мы пропускаем этот набор слов. Таким образом на одно условие становится меньше.

Если хотя бы одно из этих условий не выполняется, то возвращается FALSE.

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





Так совпало, что Сардар как раз вчера написал програмку, которая делает половину из нужной работы: http://forum.vingrad.ru/index.php?showtopi...ndpost&p=599645

Для хранения набора слов используется там дерево. Но программа предназначена только для одного дерева слов.


Sardar, вопрос к тебе Как можно сделать еще три дерева там? Или может другим путем стоит пойти?

ИМXО тебе не дерево нужно, а простая хеш-таблица, т.к. понятия "цепочка" у тебя нет, слово либо входит в множество, либо нет. Четыре хештаблицы, у четвёртой инвертируем результат поиска. Это лаба или где то понадобилось?

Цитата(Sardar @ 27.12.2005, 14:55)

Это лаба или где то понадобилось?

Это в практическом проекте понадобилось. Важна очень скорость обработки этого.
Добавлено @ 16:59

Цитата(Sardar @ 27.12.2005, 14:55)

хеш-таблица

как реализуется хеш-таблица на JavaScript?
Добавлено @ 17:00
Что подразумеваешь под цепочкой? Ведь у нас в проекте по недопущению тем с заголовками "Помогите" и т.п. - вроде, как задача 1 в 1.

Цитата(Wowa @ 27.12.2005, 15:58)

как реализуется хеш-таблица на JavaScript?

Это любой обьект, поле которого твой ключь. Таким образом можно очень быстро узнать входит ли значение во множество:

Код

function Dict() {   this.map=[]; } Dict.prototype.add=function(value) {   for(var i=0, nm; i<arguments.length; i++) {     nm='~'+arguments[i];     if(typeof(this.map[nm])=='undefined') this.map[nm]=0;     this.map[nm]++;   } } Dict.prototype.contains=function(value) {   return Boolean(this.map['~'+value]); } var d1=new Dict(); d1.add("вода", "земля", "космос"); var d2=new Dict(); d2.add("сайт", "компьютер", "интернет", "pc", "принтер"); var d3=new Dict(); d3.add("девушка", "парень", "приятель", "друг"); var d4=new Dict(); d4.add("запрещённое", "слово", "тарам-тарам"); function check(str) {     var words=str.split(/\s*,\s*/g);     var d1b=false, d2b=false, d3b=false, d4b=true;     for(var i=0; i<words.length; i++) {       if(!d1b && d1.contains(words[i])) d1b=true;       if(!d2b && d2.contains(words[i])) d2b=true;       if(!d3b && d3.contains(words[i])) d3b=true;       if(d4.contains(words[i])) d4b=false;;     }     return (d1b&&d2b&&d3b&&d4b); } alert(check("метан, чугун, вода, земля, воздух, дерево"));

Цитата(Wowa @ 27.12.2005, 15:58)

Что подразумеваешь под цепочкой?

Цепочка обьектов, вноситься понятие позиция, т.е. слово идущее сразу за другим словом.

SardarСпасибо большое! Сейчас буду эксперементировать дальше

Я вставил Алерт, чтобы вывести значение переменной, т.к. почему-то всегда false выдается.

var words=str.split(/\s*,\s*/g);
alert(words[0]);
но вместо русских букв - вопросы. Кодировку пробовал windows-1251 и utf-8 ставить. Не помогает.[s]

WinXP и старшие все на юникоде поставлены, кракозябр быть не должно. Иначе ничего не поделаешь, придёться getElementById('test').innerHTML=words[0];, где у тебя в документе (выше по определению чем <script>) толжен быть элемент с id='test'

Цитата(Wowa @ 27.12.2005, 17:48)

т.к. почему-то всегда false выдается.

Во втором и в третьем списке нет слов из тестовой строки, по условию должно быть (1&2&3&!4)

Sardar А как можно определить содержатся ли элементы в d1, d2, d3 ?

Я попробовал так, но не работает )) sizeof - не определен...

Код

Dict.prototype.sizeof=function(value) {   return sizeof(this.map); }

Добавлено @ 19:18
Просто
return (d1b&&d2b&&d3b&&d4b);
означет ведь, что TRUE будет возвращено только когда все значения true.

получается, что если
d1, d2 или d3 без элементов, то мне нужно в этой строчке:
var d1b=false, d2b=false, d3b=false, d4b=true;

давать им не false значение, а true.

или кто-нибудь видит еще решение этой проблемы?

P.S. С русским языков разобрался. Просто редактор чето-то не в той кодировке написал.

я придумал решение проблемы. Dict.prototype.add просто после добавления элементов делает return (arguments.length);


Остался всего еще один вопрос с кодировкой. Будет ли скрипт корректно работать, если он сохранен в отдельном файле вместе с данными в кодировке utf-8, но он подключается к странице, которая в кодировке windows-1251. ?

Цитата(Wowa @ 27.12.2005, 18:16)

Sardar А как можно определить содержатся ли элементы в d1, d2, d3 ?

Метод contains - возвращает true если значение во множестве, map.length даёт количество элементов во множестве, луше описать конечно своим методом.

Цитата(Wowa @ 27.12.2005, 18:16)

означет ведь, что TRUE будет возвращено только когда все значения true.

Да, по логике вещей: пробегая по всем словам смотрим входит ли слово в 1 из первых трёх множеств, если да, то флаг под множеством устанавливаеться в true; флаг под множеством 4 сбрасываеться в false если значение содержиться во множестве 4. Таково было задание в твоём первом посте. Меняя флаги ты нарушаешь логику, тогда я не понял в чём задача была...

С кодировкой проблем под JS нет, т.к. все строки в юникоде. Нужно что бы скрипт был сохранён в той же кодировке что и страница, либо задавай тегу script аттрибут charset по моему.

Строки бьються под старой виндой, т.к. системное окошко alert не принимало юникод, потому всё уходило в кракозябры. Под IE6.0 проблем не будет. В повседневной жизни alert не юзаем, выводи все мессаги в страницу, alert только для ошибок.

Цитата(Sardar @ 27.12.2005, 18:24)

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

Флаги менять нужно из-за этого:

Цитата(Wowa @ 27.12.2005, 14:11)

Очень важное дополнение: Если в каком-либо наборе слов вообще нет слов, то мы пропускаем этот набор слов. Таким образом на одно условие становится меньше.

Цитата(Sardar @ 27.12.2005, 18:24)

Нужно что бы скрипт был сохранён в той же кодировке что и страница, либо задавай тегу script аттрибут charset по моему.

ясно.
Добавлено @ 20:28
Я сделал подобным образом:

Код

if (d1.add("test", "тест") == 0) {d1b=true;} else {d1b=false;};

Вроде работает

Цитата(Wowa @ 27.12.2005, 19:27)

Я сделал подобным образом:

В моём коде add ничего не возвращает и == 0 всегда будет возвращать true...

я ведь писал выше

Цитата(Wowa @ 27.12.2005, 18:10)

я придумал решение проблемы. Dict.prototype.add просто после добавления элементов делает return (arguments.length);

Wowa

Как вариант. Массив d содержит все словари, первым элементом массива идёт словарь запрещённых слов. Остальное вроде понятно.

Код

function F(s, d, t) {return ((t + d.join(t) + t).indexOf(s) != -1)} function FF() {   var d = [['нельзя', 'запрещено'],['сайт', 'компьютер'],['девушка', 'парень'],['вода', 'земля']],       a = arguments[0].split(/\s*,\s*/g), t = ';;;', i, j, s, f;   for (i = 0; i < a.length; i++) {     s = t + a[i] + t;     if (F(s, d[0], t)) return false;     if (f != 1) {       for (j = 1; j < d.length; j++) {           if (F(s, d[j], t)) {f = 1; break}       }     }   }   return (f == 1) ? true : false; } alert(FF('метан, вода, воздух, дерево, сайт, друг'));

Zeroglif Спасибо. А как ты думаешь, какой вариант быстрее?

Цитата(Wowa @ 28.12.2005, 01:28)

А как ты думаешь, какой вариант быстрее?

А не надо думать, надо проверять: http://forum.vingrad.ru/index.php?act=modu...el&article=1270

Wowa

На глаз не скажу. Насколько я понял у тебя объёмы не сильно большие, надеюсь, должно быть быстро. Во всяком случае join() работает очень быстро, indexOf() тоже. Ну, можно ещё array.length в переменную вытащить, потому как IE это любит, функции объединить, передавать исходный текст уже массивом...


Вопрос к уважаемым властям - нельзя ли в подсветке кода (Javascript) изменить цвет для string в одинарных кавычках, дабы числа не сливались?

Код

z = 1+'1'+1+'текст'+111+'111';