source: trunk/CrypPlugins/CostFunction/CostFunction.cs @ 1204

Last change on this file since 1204 was 1204, checked in by Sven Rech, 12 years ago

small cost function entropy optimization

File size: 21.1 KB
Line 
1/*                             
2   Copyright 2009 Team CrypTool (Sven Rech,Dennis Nolte,Raoul Falk,Nils Kopal), Uni Duisburg-Essen
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16
17using System;
18using System.Collections.Generic;
19using System.Linq;
20using System.Text;
21using Cryptool.PluginBase.Cryptography;
22using Cryptool.PluginBase;
23using Cryptool.PluginBase.Miscellaneous;
24using Cryptool.PluginBase.Analysis;
25using System.ComponentModel;
26using Cryptool.PluginBase.Control;
27using System.IO;
28using System.Text.RegularExpressions;
29using System.Threading;
30namespace Cryptool.Plugins.CostFunction
31{
32    [Author("Nils Kopal", "Nils.Kopal@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
33    [PluginInfo(false, "CostFunction", "CostFunction", null, "CostFunction/icon.png")]
34    public class CostFunction : IAnalysisMisc
35    {
36        #region private variables
37        private CostFunctionSettings settings = new CostFunctionSettings();
38        private byte[] inputText = null;
39        private byte[] outputText = null;
40        private double value = 0;
41        private Boolean stopped = true;
42        private IControlCost controlSlave;
43        private String bigramInput;
44        private double[,] bigramMatrix;
45        private IDictionary<string, double[]> corpusGrams;
46
47        private DataManager dataMgr = new DataManager();
48        private const string DATATYPE = "transposition";
49
50        private IDictionary<String, DataFileMetaInfo> txtList;
51        private IDictionary<int, IDictionary<string, double[]>> statistics;
52
53        #endregion
54        #region internal constants
55        internal const int ABSOLUTE = 0;
56        internal const int PERCENTAGED = 1;
57        internal const int LOG2 = 2;
58        internal const int SINKOV = 3;
59        #endregion
60        #region CostFunctionInOut
61
62        [PropertyInfo(Direction.InputData, "Text Input", "Input your Text here", "", DisplayLevel.Beginner)]
63        public byte[] InputText
64        {
65            get
66            {
67                return inputText;
68            }
69            set
70            {
71                this.inputText = value;
72                OnPropertyChanged("InputText");
73            }
74        }
75
76        [PropertyInfo(Direction.OutputData, "Text Output", "Your Text will be send here", "", DisplayLevel.Beginner)]
77        public byte[] OutputText
78        {
79            get
80            {
81                return outputText;
82            }
83            set
84            {
85                this.outputText = value;
86                OnPropertyChanged("OutputText");
87            }
88        }
89
90        [PropertyInfo(Direction.OutputData, "Value", "The value of the function will be send here", "", DisplayLevel.Beginner)]
91        public double Value
92        {
93            get
94            {
95                return value;
96            }
97            set
98            {
99                this.value = value;
100                OnPropertyChanged("Value");
101            }
102        }
103
104        [PropertyInfo(Direction.ControlSlave, "SDES Slave", "Direct access to SDES.", "", DisplayLevel.Beginner)]
105        public IControlCost ControlSlave
106        {
107            get
108            {
109                if (controlSlave == null)
110                    controlSlave = new CostFunctionControl(this);
111                return controlSlave;
112            }
113        }
114
115        #endregion
116
117        #region IPlugin Members
118
119        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
120        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
121
122
123        public ISettings Settings
124        {
125            get { return this.settings; }
126            set { this.settings = (CostFunctionSettings)value; }
127        }
128
129        public System.Windows.Controls.UserControl Presentation
130        {
131            get { return null; }
132        }
133
134        public System.Windows.Controls.UserControl QuickWatchPresentation
135        {
136            get { return null; }
137        }
138
139        public void PreExecution()
140        {
141            this.stopped = false;
142        }
143
144        public void Execute()
145        {
146            if (this.InputText is Object && this.stopped == false)
147            {
148                int bytesToUse = 0;
149                try
150                {
151                    bytesToUse = int.Parse(settings.BytesToUse);
152                }
153                catch (Exception ex)
154                {
155                    GuiLogMessage("Entered bytesToUse is not an integer: " + ex.Message, NotificationLevel.Error);
156                    return;
157                }
158
159                if (bytesToUse > this.InputText.Length)
160                {
161                    bytesToUse = 0;
162                }
163
164                byte[] array;
165
166                if (bytesToUse > 0)
167                {
168                    //Create a new Array of size of bytesToUse if needed
169                    array = new byte[bytesToUse];
170                    for (int i = 0; i < bytesToUse && i < this.InputText.Length; i++)
171                    {
172                        array[i] = InputText[i];
173                    }
174                }
175                else
176                {
177                    array = this.InputText;
178                }
179
180                ProgressChanged(0.5, 1);
181                bigramInput = ByteArrayToString(array);
182                switch (settings.FunctionType)
183                {
184
185                    case 0: // Index of Coincedence
186                        this.Value = calculateIndexOfCoincidence(array);
187                        break;
188
189                    case 1: // Entropy
190                        this.Value = calculateEntropy(array);
191                        break;
192
193                    case 2: // Log 2 Bigrams
194                        this.Value = calculateNGrams(bigramInput, 2, 2);
195                        break;
196
197                    case 3: // sinkov Bigrams
198                        this.Value = calculateNGrams(bigramInput, 2, 3);
199                        break;
200                    case 4: //percentaged Bigrams
201                        this.Value = calculateNGrams(bigramInput, 2, 1);
202                        break;
203                    case 5: //regular expressions
204                        this.Value = regex(bigramInput);
205                        break;
206                    default:
207                        this.Value = -1;
208                        break;
209                }//end switch               
210
211                this.OutputText = this.InputText;
212                ProgressChanged(1, 1);
213
214            }//end if
215
216        }//end Execute
217
218
219        public void PostExecution()
220        {
221            this.stopped = true;
222        }
223
224        public void Pause()
225        {
226
227        }
228
229        public void Stop()
230        {
231            this.stopped = false;
232        }
233
234        public void Initialize()
235        {
236
237        }
238
239        public void Dispose()
240        {
241
242        }
243
244        #endregion
245
246        #region INotifyPropertyChanged Members
247
248        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
249
250        public void OnPropertyChanged(string name)
251        {
252            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
253        }
254
255        private void ProgressChanged(double value, double max)
256        {
257            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
258        }
259
260        public void GuiLogMessage(string p, NotificationLevel notificationLevel)
261        {
262            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
263        }
264
265        #endregion
266
267        #region IPlugin Members
268
269        public event StatusChangedEventHandler OnPluginStatusChanged;
270
271        #endregion
272
273        #region private methods
274
275
276        //public double contains(string input)
277        //{
278        //    if (settings.Contains == null)
279        //    {
280        //        GuiLogMessage("There is no text to be searched for. Please insert text in the 'Contains text / Regular Expression' - Textarea", NotificationLevel.Error);
281        //        return new Double();
282        //    }
283
284        //    if (input.Contains(settings.Contains))
285        //    {
286        //        return 1.0;
287        //    }
288        //    return -1.0;
289        //}
290
291        public double regex(string input)
292        {
293            if (settings.RegEx == null)
294            {
295                GuiLogMessage("There is no Regular Expression to be searched for. Please insert regex in the 'Regular Expression' - Textarea", NotificationLevel.Error);
296                return new Double();
297            }
298            try
299            {
300                Match match = Regex.Match(input, settings.RegEx);
301                if (match.Success)
302                {
303                    return 1.0;
304                }
305                else
306                {
307                    return -1.0;
308                }
309            }
310            catch (Exception e)
311            {
312                GuiLogMessage(e.Message, NotificationLevel.Error);
313                return -1.0;
314            }
315
316        }
317
318
319        /// <summary>
320        /// Calculates the Index of Coincidence multiplied with 100 of
321        /// a given byte array
322        ///
323        /// for example a German text has about 7.62
324        ///           an English text has about 6.61
325        /// </summary>
326        /// <param name="text">text to use</param>
327        /// <returns>Index of Coincidence</returns>
328        public double calculateIndexOfCoincidence(byte[] text)
329        {
330            return calculateIndexOfCoincidence(text, text.Length);
331        }
332
333        /// <summary>
334        /// Calculates the Index of Coincidence multiplied with 100 of
335        /// a given byte array
336        ///
337        /// for example a German text has about 7.62
338        ///           an English text has about 6.61
339        /// </summary>
340        /// <param name="text">text to use</param>
341        /// <param name="text">bytesToUse</param>
342        /// <returns>Index of Coincidence</returns>
343        public double calculateIndexOfCoincidence(byte[] text, int bytesToUse)
344        {           
345            if (bytesToUse > text.Length)
346                bytesToUse = text.Length;
347
348            double[] n = new double[256];
349            //count all ASCII symbols
350            int counter = 0;
351            foreach (byte b in text)
352            {
353                n[b]++;
354                counter++;
355                if (counter == bytesToUse)
356                    break;
357            }
358
359            double coindex = 0;
360            //sum them
361            for (int i = 0; i < n.Length; i++)
362            {
363                coindex = coindex + n[i] * (n[i] - 1);
364            }
365
366            coindex = coindex / (bytesToUse);
367            coindex = coindex / (bytesToUse - 1);
368
369            return coindex * 100;
370
371        }//end calculateIndexOfCoincidence
372
373
374        private int lastUsedSize = -1;
375        private double[] xlogx;
376        private Mutex prepareMutex = new Mutex();
377
378        private void prepareEntropy(int size)
379        {
380            xlogx = new double[size + 1];
381            //precomputations for fast entropy calculation     
382            xlogx[0] = 0.0;
383            for (int i = 1; i <= size; i++)
384                xlogx[i] = -1.0 * i * Math.Log(i / (double)size) / Math.Log(2.0);
385        }
386
387        /// <summary>
388        /// Calculates the Entropy of a given byte array
389        /// for example a German text has about 4.0629
390        /// </summary>
391        /// <param name="text">text to use</param>
392        /// <returns>Entropy</returns>
393        public double calculateEntropy(byte[] text)
394        {
395            return calculateEntropy(text, text.Length);
396        }
397
398        /// <summary>
399        /// Calculates the Entropy of a given byte array
400        /// for example a German text has about 4.0629
401        /// </summary>
402        /// <param name="text">text to use</param>
403        /// <returns>Entropy</returns>
404        public double calculateEntropy(byte[] text, int bytesToUse)
405        {
406            if (bytesToUse > text.Length)
407                bytesToUse = text.Length;
408
409            if (lastUsedSize != bytesToUse)
410            {
411                try
412                {
413                    prepareMutex.WaitOne();
414                    if (lastUsedSize != bytesToUse)
415                    {
416                        prepareEntropy(bytesToUse);
417                        lastUsedSize = bytesToUse;
418                    }
419                }
420                finally
421                {
422                    prepareMutex.ReleaseMutex();
423                }
424            }
425
426            int[] n = new int[256];
427            //count all ASCII symbols
428            for (int counter = 0; counter < bytesToUse; counter++)
429            {
430                n[text[counter]]++;
431            }
432
433            double entropy = 0;
434            //calculate probabilities and sum entropy
435            for (int i = 0; i < 256; i++)
436                entropy += xlogx[n[i]];
437
438            return entropy / (double)bytesToUse;
439
440        }//end calculateEntropy
441
442        /// <summary>
443        /// This method calculates a trigram log2 score of a given text on the basis of a given grams dictionary.
444        /// Case is insensitive.
445        /// </summary>
446        /// <param name="input">The text to be scored</param>
447        /// <param name="length">n-gram length</param>
448        /// <returns>The trigram score result</returns>
449        public double calculateNGrams(string input, int length, int valueSelection)
450        {
451            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
452            double score = 0;
453            if (corpusGrams == null)
454            { corpusGrams = GetStatistics(length); }
455            input = input.ToUpper();
456            // FIXME: case handling?
457
458            HashSet<string> inputGrams = new HashSet<string>();
459
460            foreach (string g in GramTokenizer.tokenize(input, length, false))
461            {
462                // ensure each n-gram is counted only once
463                if (inputGrams.Add(g))
464                {
465                    if (corpusGrams.ContainsKey(g))
466                    {
467                        score += corpusGrams[g][valueSelection];
468
469                    }
470                }
471            }
472
473            return score;
474        }
475        public IDictionary<string, double[]> GetStatistics(int gramLength)
476        {
477            // FIXME: inputTriGrams is not being used!
478
479            // FIXME: implement exception handling
480            if (!statistics.ContainsKey(gramLength))
481            {
482                //GuiLogMessage("Trying to load default statistics for " + gramLength + "-grams", NotificationLevel.Info);
483                statistics[gramLength] = LoadDefaultStatistics(gramLength);
484            }
485
486            return statistics[gramLength];
487        }
488
489        private IDictionary<string, double[]> LoadDefaultStatistics(int length)
490        {
491            txtList = dataMgr.LoadDirectory(DATATYPE);
492
493            return calculateAbsolutes(txtList["2gram.txt"].DataFile.FullName);
494        }
495
496        private IDictionary<string, double[]> calculateAbsolutes(String path)
497        {
498
499
500            Dictionary<string, double[]> grams = new Dictionary<string, double[]>();
501
502            StreamReader reader = new StreamReader(path);
503            String text = reader.ReadToEnd();
504
505            text.ToUpper();
506            text = Regex.Replace(text, "[^A-Z]*", "");
507
508
509            for (int i = 0; i < text.Length - 1; i++)
510            {
511                char a = text[i];
512                char b = text[i + 1];
513                String key = a.ToString();
514                key = key + b.ToString();
515
516                if (!grams.ContainsKey(key))
517                {
518                    grams.Add(key, new double[] { 1, 0, 0, 0 });
519                }
520                else
521                {
522                    grams[key][0] = grams[key][0] + 1.0;
523                }
524            }
525
526            double sum = grams.Values.Sum(item => item[ABSOLUTE]);
527            GuiLogMessage("Sum of all n-gram counts is: " + sum, NotificationLevel.Debug);
528
529            // calculate scaled values
530            foreach (double[] g in grams.Values)
531            {
532                g[PERCENTAGED] = g[ABSOLUTE] / sum;
533                g[LOG2] = Math.Log(g[ABSOLUTE], 2);
534                g[SINKOV] = Math.Log(g[PERCENTAGED], Math.E);
535            }
536
537
538
539            return grams;
540        }
541
542        public string ByteArrayToString(byte[] arr)
543        {
544            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
545            return enc.GetString(arr);
546        }
547
548
549        #endregion
550
551
552    }
553
554    #region slave
555
556    public class CostFunctionControl : IControlCost
557    {
558        public event IControlStatusChangedEventHandler OnStatusChanged;
559        #region IControlCost Members
560
561        private CostFunction plugin;
562
563        #endregion
564
565        /// <summary>
566        /// Constructor
567        /// </summary>
568        /// <param name="plugin"></param>
569        public CostFunctionControl(CostFunction plugin)
570        {
571            this.plugin = plugin;
572        }
573
574        public int getBytesToUse()
575        {
576            try
577            {
578                return int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
579            }
580            catch (Exception ex)
581            {
582                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
583            }
584        }
585
586        /// <summary>
587        /// Returns the relation operator of the cost function which is set by by CostFunctionSettings
588        /// </summary>
589        /// <returns>RelationOperator</returns>
590        public RelationOperator getRelationOperator()
591        {
592            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
593            {
594                case 0: //Index of coincidence
595                    return RelationOperator.LargerThen;
596                case 1: //Entropy
597                    return RelationOperator.LessThen;
598                case 2: // Bigrams: log 2
599                    return RelationOperator.LessThen;
600                case 3: // Sinkov
601                    return RelationOperator.LargerThen;
602                case 4: // percentage
603                    return RelationOperator.LargerThen;
604                case 5: // Regular Expression
605                    return RelationOperator.LargerThen;
606                default:
607                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
608            }//end switch
609        }//end getRelationOperator
610
611        /// <summary>
612        /// Calculates the cost function of the given text
613        ///
614        /// Cost function can be set by CostFunctionSettings
615        /// This algorithm uses a bytesToUse which can be set by CostFunctionSettings
616        /// If bytesToUse is set to 0 it uses the whole text
617        ///
618        /// </summary>
619        /// <param name="text"></param>
620        /// <returns>cost</returns>
621        public double calculateCost(byte[] text)
622        {
623            int bytesToUse = 0;
624            try
625            {
626                bytesToUse = ((CostFunctionSettings)this.plugin.Settings).BytesToUseInteger;
627            }
628            catch (Exception ex)
629            {
630                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
631            }
632
633            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
634            {
635                case 0: //Index of coincidence
636                    return plugin.calculateIndexOfCoincidence(text, bytesToUse);
637                case 1: //Entropy
638                    return plugin.calculateEntropy(text, bytesToUse);
639                case 2: // Bigrams: log 2
640                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 2);
641                case 3: // Bigrams: Sinkov
642                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 3);
643                case 4: // Bigrams: Percentaged
644                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 1);
645                case 5: // regular expression
646                    return plugin.regex(plugin.ByteArrayToString(text));
647                default:
648                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
649            }//end switch
650        }
651
652
653    #endregion
654    }
655
656}
657
Note: See TracBrowser for help on using the repository browser.