Я ищу шаблон, алгоритм или библиотеку, которая возьмет набор дат и вернет описание повторения, если один из них выйдет, т.е. набор [11-01-2010, 11-08-2010, 11- 15-2010, 11-22-2010, 11-29-2010] даст что-то вроде "Каждый понедельник ноября".
Кто-нибудь видел что-либо подобное раньше или какие-либо предложения по его эффективному использованию?
Грамматическая эволюция (GE) подходит для такого рода проблем, потому что вы ищете ответ, который придерживается определенного языка. Грамматическая эволюция также используется для генерации программ, составления музыки, проектирования и т.д.
Я бы подошел к такой задаче:
Структура пространства проблем с грамматикой.
Построить Грамматика без контекста, которая может представлять все желаемые шаблоны повторения. Рассмотрим такие правила производства:
datepattern -> datepattern 'and' datepattern
datepattern -> frequency bounds
frequency -> 'every' ordinal weekday 'of the month'
frequency -> 'every' weekday
ordinal -> ordinal 'and' ordinal
ordinal -> 'first' | 'second' | 'third'
bounds -> 'in the year' year
Примером шаблона, созданного этими правилами, является: "каждую вторую и третью среду месяца в 2010 году и каждый вторник в 2011 году"
Один из способов реализации такой грамматики - через иерархию классов, которую вы позже будете использовать с помощью отражения, как я сделал в примере ниже.
Отобразить этот язык на набор дат
Вам следует создать функцию, которая принимает предложение с вашего языка и рекурсивно возвращает набор всех дат, охватываемых им. Это позволяет сравнить ваши ответы на ввод.
Руководствуясь грамматикой, найдите потенциальные решения
Вы можете использовать генетический алгоритм или симулированный отжиг для соответствия датам грамматике, попробуйте удачу с помощью динамического программирования или просто начните с перечисления грубой силы по всем возможным предложениям.
Если вы идете с генетическим алгоритмом, ваша концепция мутации должна состоять из подстановки выражения для другого, основанного на применении одного из ваших производственных правил.
Взгляните на следующие сайты, связанные с GE, для кода и информации:
http://www.bangor.ac.uk/~eep201/jge/
http://nohejl.name/age/
http://www.geneticprogramming.us/Home_Page.html
Оценить каждое решение
Функция фитнеса может учитывать текстовую длину решения, количество дат, сгенерированных более одного раза, количество пропущенных дат, а также количество созданных неправильных дат.
Пример кода
По просьбе, и поскольку это такая интересная задача, я написал рудиментарную реализацию алгоритма, чтобы вы начали. Хотя он работает, он ни в коем случае не завершен, дизайн должен окончательно задуматься, и после того, как вы почерпнули основные выводы из этого примера, я рекомендую вам рассмотреть использование библиотек, упомянутых выше.
/// <summary>
/// This is a very basic example implementation of a grammatical evolution algorithm for formulating a recurrence pattern in a set of dates.
/// It needs significant extensions and optimizations to be useful in a production setting.
/// </summary>
static class Program
{
#region "Class hierarchy that codifies the grammar"
class DatePattern
{
public Frequency frequency;
public Bounds bounds;
public override string ToString() { return "" + frequency + " " + bounds; }
public IEnumerable<DateTime> Dates()
{
return frequency == null ? new DateTime[] { } : frequency.FilterDates(bounds.GetDates());
}
}
abstract class Bounds
{
public abstract IEnumerable<DateTime> GetDates();
}
class YearBounds : Bounds
{
/* in the year .. */
public int year;
public override string ToString() { return "in the year " + year; }
public override IEnumerable<DateTime> GetDates()
{
var firstDayOfYear = new DateTime(year, 1, 1);
return Enumerable.Range(0, new DateTime(year, 12, 31).DayOfYear)
.Select(dayOfYear => firstDayOfYear.AddDays(dayOfYear));
}
}
abstract class Frequency
{
public abstract IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates);
}
class WeeklyFrequency : Frequency
{
/* every .. */
public DayOfWeek dayOfWeek;
public override string ToString() { return "every " + dayOfWeek; }
public override IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates)
{
return Dates.Where(date => (date.DayOfWeek == dayOfWeek));
}
}
class MonthlyFrequency : Frequency
{
/* every .. */
public Ordinal ordinal;
public DayOfWeek dayOfWeek;
/* .. of the month */
public override string ToString() { return "every " + ordinal + " " + dayOfWeek + " of the month"; }
public override IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates)
{
return Dates.Where(date => (date.DayOfWeek == dayOfWeek) && (int)ordinal == (date.Day - 1) / 7);
}
}
enum Ordinal { First, Second, Third, Fourth, Fifth }
#endregion
static Random random = new Random();
const double MUTATION_RATE = 0.3;
static Dictionary<Type, Type[]> subtypes = new Dictionary<Type, Type[]>();
static void Main()
{
// The input signifies the recurrence 'every first thursday of the month in 2010':
var input = new DateTime[] {new DateTime(2010,12,2), new DateTime(2010,11,4),new DateTime(2010,10,7),new DateTime(2010,9,2),
new DateTime(2010,8,5),new DateTime(2010,7,1),new DateTime(2010,6,3),new DateTime(2010,5,6),
new DateTime(2010,4,1),new DateTime(2010,3,4),new DateTime(2010,2,4),new DateTime(2010,1,7) };
for (int cTests = 0; cTests < 20; cTests++)
{
// Initialize with a random population
int treesize = 0;
var population = new DatePattern[] { (DatePattern)Generate(typeof(DatePattern), ref treesize), (DatePattern)Generate(typeof(DatePattern), ref treesize), (DatePattern)Generate(typeof(DatePattern), ref treesize) };
Run(input, new List<DatePattern>(population));
}
}
private static void Run(DateTime[] input, List<DatePattern> population)
{
var strongest = population[0];
int strongestFitness = int.MinValue;
int bestTry = int.MaxValue;
for (int cGenerations = 0; cGenerations < 300 && strongestFitness < -100; cGenerations++)
{
// Select the best individuals to survive:
var survivers = population
.Select(individual => new { Fitness = Fitness(input, individual), individual })
.OrderByDescending(pair => pair.Fitness)
.Take(5)
.Select(pair => pair.individual)
.ToArray();
population.Clear();
// The survivers are the foundation for the next generation:
foreach (var parent in survivers)
{
for (int cChildren = 0; cChildren < 3; cChildren++)
{
int treeSize = 1;
DatePattern child = (DatePattern)Mutate(parent, ref treeSize); // NB: procreation may also be done through crossover.
population.Add((DatePattern)child);
var childFitness = Fitness(input, child);
if (childFitness > strongestFitness)
{
bestTry = cGenerations;
strongestFitness = childFitness;
strongest = child;
}
}
}
}
Trace.WriteLine("Found best match with fitness " + Fitness(input, strongest) + " after " + bestTry + " generations: " + strongest);
}
private static object Mutate(object original, ref int treeSize)
{
treeSize = 0;
object replacement = Construct(original.GetType());
foreach (var field in original.GetType().GetFields())
{
object newFieldValue = field.GetValue(original);
int subtreeSize;
if (field.FieldType.IsEnum)
{
subtreeSize = 1;
if (random.NextDouble() <= MUTATION_RATE)
newFieldValue = ConstructRandomEnumValue(field.FieldType);
}
else if (field.FieldType == typeof(int))
{
subtreeSize = 1;
if (random.NextDouble() <= MUTATION_RATE)
newFieldValue = (random.Next(2) == 0
? Math.Min(int.MaxValue - 1, (int)newFieldValue) + 1
: Math.Max(int.MinValue + 1, (int)newFieldValue) - 1);
}
else
{
subtreeSize = 0;
newFieldValue = Mutate(field.GetValue(original), ref subtreeSize); // mutate pre-maturely to find out subtreeSize
if (random.NextDouble() <= MUTATION_RATE / subtreeSize) // makes high-level nodes mutate less.
{
subtreeSize = 0; // init so we can track the size of the subtree soon to be made.
newFieldValue = Generate(field.FieldType, ref subtreeSize);
}
}
field.SetValue(replacement, newFieldValue);
treeSize += subtreeSize;
}
return replacement;
}
private static object ConstructRandomEnumValue(Type type)
{
var vals = type.GetEnumValues();
return vals.GetValue(random.Next(vals.Length));
}
private static object Construct(Type type)
{
return type.GetConstructor(new Type[] { }).Invoke(new object[] { });
}
private static object Generate(Type type, ref int treesize)
{
if (type.IsEnum)
{
return ConstructRandomEnumValue(type);
}
else if (typeof(int) == type)
{
return random.Next(10) + 2005;
}
else
{
if (type.IsAbstract)
{
// pick one of the concrete subtypes:
var subtypes = GetConcreteSubtypes(type);
type = subtypes[random.Next(subtypes.Length)];
}
object newobj = Construct(type);
foreach (var field in type.GetFields())
{
treesize++;
field.SetValue(newobj, Generate(field.FieldType, ref treesize));
}
return newobj;
}
}
private static int Fitness(DateTime[] input, DatePattern individual)
{
var output = individual.Dates().ToArray();
var avgDateDiff = Math.Abs((output.Average(d => d.Ticks / (24.0 * 60 * 60 * 10000000)) - input.Average(d => d.Ticks / (24.0 * 60 * 60 * 10000000))));
return
-individual.ToString().Length // succinct patterns are preferred.
- input.Except(output).Count() * 300 // Forgetting some of the dates is bad.
- output.Except(input).Count() * 3000 // Spurious dates cause even more confusion to the user.
- (int)(avgDateDiff) * 30000; // The difference in average date is the most important guide.
}
private static Type[] GetConcreteSubtypes(Type supertype)
{
if (subtypes.ContainsKey(supertype))
{
return subtypes[supertype];
}
else
{
var types = AppDomain.CurrentDomain.GetAssemblies().ToList()
.SelectMany(s => s.GetTypes())
.Where(p => supertype.IsAssignableFrom(p) && !p.IsAbstract).ToArray();
subtypes.Add(supertype, types);
return types;
}
}
}
Надеюсь, это поможет вам. Обязательно поделитесь своим фактическим решением где-нибудь; Я думаю, что это будет очень полезно во множестве сценариев.
Если ваша цель состоит в том, чтобы генерировать удобочитаемые описания шаблона, как в вашем "Каждый понедельник ноября", то вы, вероятно, захотите начать с перечисления возможных описаний. Описания можно разбить на частоту и границы, например,
Частота:
Bounds:
Их будет не так много, и вы можете проверить их один за другим.
Что я буду делать:
Глядя на это, вы можете использовать либо Simulated Annealing, либо Genetic Algorithm. Кроме того, если у вас есть описания, вы можете сравнить описания для создания образца.
Вы можете получить доступ к системной дате или системной дате и времени и сконструировать грубые календарные точки в памяти на основе даты и дня недели, возвращенных результатом вызова или функции. Затем используйте количество дней в соответствующих месяцах для их суммирования и добавьте количество дней дневной переменной на вход и/или получите доступ к календарной точке на соответствующую неделю, начинающуюся с воскресенья или понедельника, и вычислите или увеличите индекс до правильного день. Построить текстовую строку с использованием фиксированных символов и вставить соответствующую переменную, такую как полное имя дня недели, по мере необходимости. Для получения всех событий, из которых должны отображаться или считаются вхождения, может быть несколько обходов.
Сначала найдите последовательность, если она существует:
step = {day,month,year}
period=0
for d = 1 to dates.count-1
interval(d,step)=datedifference(s,date(d),date(d+1))
next
' Find frequency with largest interval
for s = year downto day
found=true
for d = 1 to dates.count-2
if interval(d,s)=interval(d+1,s) then
found=false
exit for
end if
next
if found then
period=s
frequency=interval(1,s)
exit for
end if
next
if period>0
Select case period
case day
if frequency mod 7 = 0 then
say "every" dayname(date(1))
else
say "every" frequency "days"
end if
case month
say "every" frequency "months on day" daynumber(date(1))
case years
say "every" frequency "years on" daynumber(date(1)) monthname(date(1))
end select
end if
Наконец, сделка с "в ноябре", "с 2007 по 2010 год" и т.д. должна быть очевидной.
НТН
Мне нравится @arjen answer, но я не думаю, что есть необходимость в сложном алгоритме. Это так просто. Если есть шаблон, есть шаблон... поэтому будет работать простой алгоритм. Сначала нам нужно подумать о типах моделей, которые мы ищем: ежедневно, еженедельно, ежемесячно и ежегодно.
Как распознать?
Ежедневно: есть запись каждый день Еженедельно: каждую неделю происходит запись Ежемесячно: ежемесячная запись Ежегодно: каждый год происходит запись
Сложно? Нет. Просто подсчитайте количество повторений, которые у вас есть, а затем классифицируйте.
Вот моя реализация
RecurrencePatternAnalyser.java
public class RecurrencePatternAnalyser {
// Local copy of calendars by add() method
private ArrayList<Calendar> mCalendars = new ArrayList<Calendar>();
// Used to count the uniqueness of each year/month/day
private HashMap<Integer, Integer> year_count = new HashMap<Integer,Integer>();
private HashMap<Integer, Integer> month_count = new HashMap<Integer,Integer>();
private HashMap<Integer, Integer> day_count = new HashMap<Integer,Integer>();
private HashMap<Integer, Integer> busday_count = new HashMap<Integer,Integer>();
// Used for counting payments before due date on weekends
private int day_goodpayer_ocurrences = 0;
private int day_goodPayer = 0;
// Add a new calendar to the analysis
public void add(Calendar date)
{
mCalendars.add(date);
addYear( date.get(Calendar.YEAR) );
addMonth( date.get(Calendar.MONTH) );
addDay( date.get(Calendar.DAY_OF_MONTH) );
addWeekendDays( date );
}
public void printCounts()
{
System.out.println("Year: " + getYearCount() +
" month: " + getMonthCount() + " day: " + getDayCount());
}
public RecurrencePattern getPattern()
{
int records = mCalendars.size();
if (records==1)
return null;
RecurrencePattern rp = null;
if (getYearCount()==records)
{
rp = new RecurrencePatternYearly();
if (records>=3)
rp.setConfidence(1);
else if (records==2)
rp.setConfidence(0.9f);
}
else if (getMonthCount()==records)
{
rp = new RecurrencePatternMonthly();
if (records>=12)
rp.setConfidence(1);
else
rp.setConfidence(1-(-0.0168f * records + 0.2f));
}
else
{
calcDaysRepetitionWithWeekends();
if (day_goodpayer_ocurrences==records)
{
rp = new RecurrencePatternMonthly();
rp.setPattern(RecurrencePattern.PatternType.MONTHLY_GOOD_PAYER);
if (records>=12)
rp.setConfidence(0.95f);
else
rp.setConfidence(1-(-0.0168f * records + 0.25f));
}
}
return rp;
}
// Increment one more year/month/day on each count variable
private void addYear(int key_year) { incrementHash(year_count, key_year); }
private void addMonth(int key_month) { incrementHash(month_count, key_month); }
private void addDay(int key_day) { incrementHash(day_count, key_day); }
// Retrieve number of unique entries for the records
private int getYearCount() { return year_count.size(); }
private int getMonthCount() { return month_count.size(); }
private int getDayCount() { return day_count.size(); }
// Generic function to increment the hash by 1
private void incrementHash(HashMap<Integer, Integer> var, Integer key)
{
Integer oldCount = var.get(key);
Integer newCount = 0;
if ( oldCount != null ) {
newCount = oldCount;
}
newCount++;
var.put(key, newCount);
}
// As Bank are closed during weekends, some dates might be anticipated
// to Fridays. These will be false positives for the recurrence pattern.
// This function adds Saturdays and Sundays to the count when a date is
// Friday.
private void addWeekendDays(Calendar c)
{
int key_day = c.get(Calendar.DAY_OF_MONTH);
incrementHash(busday_count, key_day);
if (c.get(Calendar.DAY_OF_WEEK) == Calendar.FRIDAY)
{
// Adds Saturday
c.add(Calendar.DATE, 1);
key_day = c.get(Calendar.DAY_OF_MONTH);
incrementHash(busday_count, key_day);
// Adds Sunday
c.add(Calendar.DATE, 1);
key_day = c.get(Calendar.DAY_OF_MONTH);
incrementHash(busday_count, key_day);
}
}
private void calcDaysRepetitionWithWeekends()
{
Iterator<Entry<Integer, Integer>> it =
busday_count.entrySet().iterator();
while (it.hasNext()) {
@SuppressWarnings("rawtypes")
Map.Entry pair = (Map.Entry)it.next();
if ((int)pair.getValue() > day_goodpayer_ocurrences)
{
day_goodpayer_ocurrences = (int) pair.getValue();
day_goodPayer = (int) pair.getKey();
}
//it.remove(); // avoids a ConcurrentModificationException
}
}
}
RecurrencePattern.java
public abstract class RecurrencePattern {
public enum PatternType {
YEARLY, MONTHLY, WEEKLY, DAILY, MONTHLY_GOOD_PAYER
}
public enum OrdinalType {
FIRST, SECOND, THIRD, FOURTH, FIFTH
}
protected PatternType pattern;
private float confidence;
private int frequency;
public PatternType getPattern() {
return pattern;
}
public void setPattern(PatternType pattern) {
this.pattern = pattern;
}
public float getConfidence() {
return confidence;
}
public void setConfidence(float confidence) {
this.confidence = confidence;
}
public int getFrequency() {
return frequency;
}
public void setFrequency(int frequency) {
this.frequency = frequency;
}
}
RecurrencePatternMonthly.java
public class RecurrencePatternMonthly extends RecurrencePattern {
private boolean isDayFixed;
private boolean isDayOrdinal;
private OrdinalType ordinaltype;
public RecurrencePatternMonthly()
{
this.pattern = PatternType.MONTHLY;
}
}
RecurrencePatternYearly.java
public class RecurrencePatternYearly extends RecurrencePattern {
private boolean isDayFixed;
private boolean isMonthFixed;
private boolean isDayOrdinal;
private OrdinalType ordinaltype;
public RecurrencePatternYearly()
{
this.pattern = PatternType.YEARLY;
}
}
Main.java
public class Algofin {
static Connection c = null;
public static void main(String[] args) {
//openConnection();
//readSqlFile();
RecurrencePatternAnalyser r = new RecurrencePatternAnalyser();
//System.out.println(new GregorianCalendar(2015,1,30).get(Calendar.MONTH));
r.add(new GregorianCalendar(2015,0,1));
r.add(new GregorianCalendar(2015,0,30));
r.add(new GregorianCalendar(2015,1,27));
r.add(new GregorianCalendar(2015,3,1));
r.add(new GregorianCalendar(2015,4,1));
r.printCounts();
RecurrencePattern rp;
rp=r.getPattern();
System.out.println("Pattern: " + rp.getPattern() + " confidence: " + rp.getConfidence());
}
}
Я думаю, вам нужно будет его построить, и я думаю, что это будет дьявол в деталях проекта. Начните с получения более тщательных требований. Какие шаблоны дат вы хотите распознать? Придумайте список примеров, которые вы хотите, чтобы ваш алгоритм успешно идентифицировал. Напишите свой алгоритм для удовлетворения ваших примеров. Поместите свои примеры в тестовый набор, поэтому, когда вы получите разные требования, вы можете убедиться, что вы не сломали старые.
Я предсказываю, что вы напишете 200 операторов if-then-else.
Хорошо, у меня есть одна идея. Ознакомьтесь с понятиями sets, unions, coverage, intersection и т.д. Имейте список коротких шаблонов, которые вы ищете, например: "Каждый день в октябре", "Каждый день в ноябре" и "Каждый день в декабре". Если эти короткие шаблоны содержатся в наборе дат, тогда определите функцию union, которая может сочетать более короткие шаблоны интеллектуальными способами. Например, допустим, вы сопоставили три шаблона, о которых я упоминал выше. Если вы union их вместе, вы получите: "Каждый день в октябре-декабре". Вы могли бы стремиться вернуть наиболее сжатый set of unions, который cover ваш набор дат или что-то в этом роде.
Посмотрите на свою любимую программу календаря. Посмотрите, какие шаблоны повторяемости событий он может генерировать. Обратный инженер их.