REMOVED: the DrawModel function from classifierInterface (they all do exactly the...
[mldemos:baraks-mldemos.git] / Core / parser.cpp
1 /*********************************************************************
2 MLDemos: A User-Friendly visualization toolkit for machine learning
3 Copyright (C) 2011 Chrstophe Paccolat
4 Contact: mldemos@b4silio.com
5
6 This library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public License,
8 version 3 as published by the Free Software Foundation.
9
10 This library is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with this library; if not, write to the Free
17 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 *********************************************************************/
19 #include <QDebug>
20 #include <basicMath.h>
21 #include "parser.h"
22
23 /* CSVRow stuff */
24
25 std::istream& operator>>(std::istream& str,CSVRow& data)
26 {
27     data.readNextRow(str);
28     return str;
29 }
30
31 std::string const& CSVRow::operator[](std::size_t index) const
32 {
33     return m_data[index];
34 }
35 std::string CSVRow::at(size_t column) const
36 {
37     return m_data.at(column);
38 }
39 std::string CSVRow::getFirstCell() const
40 {
41         if(!m_data.size()) return string();
42         return m_data.at(0);
43 }
44 std::string CSVRow::getLastCell() const
45 {
46         if(!m_data.size()) return string();
47         return m_data.back();
48 }
49 std::vector<std::string> CSVRow::getParsedLine() const
50 {
51     return m_data;
52 }
53 std::size_t CSVRow::size() const
54 {
55     return m_data.size();
56 }
57
58 void CSVRow::readNextRow(std::istream& str)
59 {
60     // read line from file
61     std::string line;
62     std::getline(str,line);
63
64     // we try using commas, semi-colons and tabs
65
66     // convert to stream
67     std::stringstream lineStream(line);
68     std::string cell;
69
70     // update row (array) content
71     m_data.clear();
72     while(std::getline(lineStream,cell,separator[0]))
73     {
74         std::string test = cell;
75         std::remove(test.begin(), test.end(), ' ');
76         if(test.empty()) continue;
77         m_data.push_back(cell);
78     }
79 }
80
81 unsigned int getType(string input)
82 {
83     if (is<unsigned int>(input))    return UNSIGNED_INT_TYPE;
84     if (is<int>(input))             return INT_TYPE;
85     if (is<float>(input))           return FLOAT_TYPE;
86     if (is<char>(input))            return CHAR_TYPE;
87     if (is<string>(input))          return STRING_TYPE;
88                                     return UNKNOWN_TYPE;
89 }
90
91 /* CSVIterator stuff */
92
93 CSVIterator::CSVIterator(std::istream& str, std::string separator)
94     : m_str(str.good()?&str:NULL), separator(separator), m_row(separator)
95 {
96     ++(*this);
97 }
98
99 CSVIterator::CSVIterator():m_str(NULL)
100 {
101 }
102
103 bool CSVIterator::eof()
104 {
105     return (m_str == NULL);
106 }
107
108 // Pre Increment
109 CSVIterator& CSVIterator::operator++()
110 {
111     if (m_str)
112     {
113         (*m_str) >> m_row;
114         m_str = m_str->good()?m_str:NULL;
115     }
116     return *this;
117 }
118 // Post increment
119 CSVIterator CSVIterator::operator++(int)
120 {
121     CSVIterator tmp(*this);
122     ++(*this);
123     return tmp;
124 }
125
126 CSVRow const& CSVIterator::operator*()   const
127 {
128     return m_row;
129 }
130
131 CSVRow const* CSVIterator::operator->()  const
132 {
133     return &m_row;
134 }
135
136 bool CSVIterator::operator!=(CSVIterator const& rhs)
137 {
138     return !((*this) == rhs);
139 }
140
141 bool CSVIterator::operator==(CSVIterator const& rhs)
142 {
143     return ((this == &rhs) || ((this->m_str == NULL) && (rhs.m_str == NULL)));
144 }
145
146 /* CSVParser stuff */
147 CSVParser::CSVParser()
148 {
149     bFirstRowAsHeader = false;
150     outputLabelColumn = 2;
151 }
152
153 void CSVParser::clear()
154 {
155     outputLabelColumn = 0;
156     classLabels.clear();
157     data.clear();
158     dataTypes.clear();
159 }
160
161 void CSVParser::parse(const char* fileName, int separatorType)
162 {
163     // init
164     uint8_t offset = getBOMsize(fileName);
165     file.open(fileName,std::ios_base::binary);
166     if(!file.is_open()) return;
167
168     std::string separators[] = {",", ";", "\t", " "};
169     int separatorCount = 4;
170     int bestSeparator = 0;
171     int dim=0;
172
173     if(!separatorType)
174     {
175         // we test the separators to find which one is best
176         for(int i=0; i<separatorCount; i++)
177         {
178             file.seekg(offset,ios::beg);
179             // Parse CSV input file
180             CSVIterator parser(file, separators[i]);
181             ++parser; // we skip the first line as it might be a header line
182             if(parser.eof() || !parser->size()) continue;
183             vector<string> parsed = parser->getParsedLine();
184             //qDebug() << "separator: " << separators[i].c_str() << ":" << parsed.size();
185             if(parsed.size() > dim)
186             {
187                 dim = parsed.size();
188                 bestSeparator = i;
189             }
190         }
191     }
192     else bestSeparator = separatorType-1;
193
194     file.seekg(offset,ios::beg);
195
196     data.clear();
197     for(CSVIterator parser(file, separators[bestSeparator]);!parser.eof(); ++parser)
198     {
199         if(!parser->size()) continue;
200         vector<string> parsed = parser->getParsedLine();
201         if(!parsed.size()) continue;
202
203         // check for remaining line carrys, *nix only
204         string::size_type pos = 0;
205 #if !(defined WIN32 || defined _WIN32)
206         while ( ( pos = parsed.back().find ("\r",pos) ) != string::npos )
207             parsed.back().erase ( pos, 1 );
208 #endif
209         // remove null character noise when coming from UTF-X
210         // we assume that the data has only ASCII characters
211         if (offset)
212             for(size_t i = 0; i < parsed.size(); i++)
213             {
214                 pos = 0;
215                 while ( ( pos = parsed.at(i).find ('\0',pos) ) != string::npos )
216                     parsed.at(i).erase ( pos, 1 );
217
218             }
219
220         // Fill dataset
221         data.push_back(parsed);
222     }
223
224     cout << "Parsing done, read " << data.size() << " entries" << endl;
225     cout << "Found " << data.at(0).size() << " input labels / columns" << endl;
226
227     // look for data types
228     for(size_t i = 0; i < data.at(1).size(); i++)
229     {
230         // Look for a non-empty cell
231         // start with 2nd row as first might be input labels
232         size_t testRow = 1;
233         while(data.at(testRow++).at(i) == "?" && testRow != data.size());
234
235
236         if (testRow == data.size())
237         {
238             // if the whole column is missing data... delete it
239             cout << "Warning: Found empty column, deleting..." << endl;
240             for (size_t j = 0; j < data.size(); j++)
241                 data.at(j).erase(data.at(j).begin()+i);
242
243         } else // save input type
244             dataTypes.push_back(getType(data.at(testRow).at(i)));
245     }
246
247     cout << data.at(0).size() << " input labels / columns remaining after cleanup" << endl;
248
249 //    cout << "Contents: " << endl;
250 //    for (size_t j=0; j<data.size(); j++)
251 //    {
252 //        cout << "|";
253 //        for (size_t i=0; i<data.at(1).size(); i++)
254 //            cout << data.at(j).at(i) << "|";
255 //        cout << endl;
256 //    }
257
258     // Read output (class) labels
259     getOutputLabelTypes(true);
260     file.close();
261 }
262
263 void CSVParser::setOutputColumn(int column)
264 {
265     outputLabelColumn = column;
266    //getOutputLabelTypes(true); // need to update output label types
267 }
268
269 map<string,unsigned int> CSVParser::getOutputLabelTypes(bool reparse)
270 {
271     if (!reparse) return classLabels;
272     unsigned int id = 0;
273     pair<map<string,unsigned int>::iterator,bool> ret;
274     // Use by default the last column as output class
275     if ((data.size() && outputLabelColumn == -1) || outputLabelColumn >= data.size()) outputLabelColumn = data.at(0).size()-1;
276     for(vector<vector<string> >::iterator it = data.begin(); it<data.end(); it++)
277     {
278         ret = classLabels.insert( pair<string,unsigned int>(it->at(outputLabelColumn),id) );
279         if (ret.second == true) id++; // new class found
280     }
281     return classLabels;
282 }
283
284 vector<size_t> CSVParser::getMissingValIndex()
285 {
286     vector<size_t> missingValIndex;
287     size_t nbCols = data.at(0).size();
288     for (size_t i = 0; i < data.size(); i++)
289         for (size_t j = 0; j < nbCols; j++)
290             if (data[i][j] == "?") missingValIndex.push_back(i);
291     return missingValIndex;
292 }
293
294 bool CSVParser::hasData()
295 {
296     return data.size();
297 }
298
299 void CSVParser::cleanData(unsigned int acceptedTypes)
300 {
301     vector<string>::iterator it_str;
302     vector<unsigned int>::iterator it_uint = dataTypes.begin();
303     for(size_t i = 0; i < dataTypes.size(); i++)
304         if (!(dataTypes[i]&acceptedTypes) &&  // data type does not correspond to a requested one
305            (i != outputLabelColumn))       // output labels are stored separately, ignore
306         {
307             cout << "Removing colum " << i << " of type " << dataTypes[i] <<  " ... ";
308             for(size_t j = 0; j < data.size(); j++)
309             {
310                 /* @note it seems that if we have --i instead of (i-1), the compiler produces bad code (SIGSEGV) */
311                 it_str = data.at(j).begin() + (i-1);
312                 data.at(j).erase(it_str); // delete the column
313             }
314             cout << "and matching type reference ...  " ;
315             it_uint = dataTypes.begin() + (i-1);
316             dataTypes.erase(it_uint); // delete the input to stay consistant
317             i--; if (i < outputLabelColumn) outputLabelColumn--;
318         }
319 }
320
321 pair<vector<fvec>,ivec> CSVParser::getData(ivec excludeIndex, int maxSamples)
322 {
323     int count = data.size();
324     if(bFirstRowAsHeader) count--;
325     int headerSkip = bFirstRowAsHeader?1:0;
326     if(count <= 0) return pair<vector<fvec>,ivec>();
327     vector<fvec> samples(count);
328     ivec labels(count);
329     int dim = data[0].size();
330     if(outputLabelColumn != -1) outputLabelColumn = min(dim-1, outputLabelColumn);
331     classNames.clear();
332     vector< map<string,int> > labelMaps(dim);
333     ivec labelCounters(dim,0);
334     pair<map<string,int>::iterator,bool> ret;
335     FOR(i, data.size())
336     {
337         if(!i && bFirstRowAsHeader) continue;
338         // check if it's always a number
339         fvec& sample = samples[i-headerSkip];
340         sample.resize((outputLabelColumn==-1) ? dim : dim-1);
341         FOR(j, dim)
342         {
343             QString s(data[i][j].c_str());
344             bool ok;
345             float val = s.toFloat(&ok);
346             if(j==outputLabelColumn || !ok)
347             {
348                 if(labelMaps[j].count(data[i][j]) > 0) val = labelMaps[j][data[i][j]];
349                 else
350                 {
351                     val = (float)labelCounters[j];
352                     ret = labelMaps[j].insert(pair<string,int>(data[i][j], val));
353                     if(ret.second) labelCounters[j]++;
354                 }
355             }
356             if(j!=outputLabelColumn)
357             {
358                 if(outputLabelColumn==-1) sample[j] = val;
359                 else
360                 {
361                     int index = j < outputLabelColumn ? j : j-1;
362                     sample[index] = val;
363                 }
364             }
365         }
366     }
367
368     if(labelMaps[outputLabelColumn].size() && outputLabelColumn != -1)
369     {
370         bool bNumerical = true;
371         FORIT(labelMaps[outputLabelColumn], string, int)
372         {
373             bool ok;
374             QString(it->first.c_str()).toFloat(&ok);
375             if(!ok)
376             {
377                 bNumerical = false;
378                 break;
379             }
380         }
381         if(!bNumerical)
382         {
383             FORIT(labelMaps[outputLabelColumn], string, int)
384             {
385                 classNames[it->second] = QString(it->first.c_str());
386                 //else classNames[it->second] = QString("Class %1").arg(QString(it->first.c_str()).toFloat());
387             }
388         }
389         else classNames.clear();
390     }
391     if(outputLabelColumn == -1)
392     {
393         FOR(i, data.size())
394         {
395             if(!i && bFirstRowAsHeader) continue;
396             labels[i-headerSkip] = 0;
397         }
398     }
399     else
400     {
401         /*
402         qDebug() << "label indices";
403         for(map<string,int>::iterator it = labelMaps[outputLabelColumn].begin(); it != labelMaps[outputLabelColumn].end(); it++)
404         {
405             qDebug() << (it->first).c_str() << " " << it->second;
406         }
407         */
408         bool numerical = true;
409         FOR(i, data.size())
410         {
411             if(!i && bFirstRowAsHeader) continue;
412             bool ok;
413             float val = QString(data[i][outputLabelColumn].c_str()).toFloat(&ok);
414             if(!ok)
415             {
416                 numerical = false;
417                 break;
418             }
419         }
420         FOR(i, data.size())
421         {
422             if(!i && bFirstRowAsHeader) continue;
423             bool ok;
424             float val = QString(data[i][outputLabelColumn].c_str()).toFloat(&ok);
425             if(numerical)
426             {
427                 labels[i-headerSkip] = val;
428             }
429             else
430             {
431                 int label = labelMaps[outputLabelColumn][data[i][outputLabelColumn]];
432                 labels[i-headerSkip] = label;
433             }
434         }
435     }
436     if(maxSamples != -1 && maxSamples < samples.size())
437     {
438         vector<fvec> newSamples(maxSamples);
439         ivec newLabels(maxSamples);
440         u32 *perm = randPerm(maxSamples);
441         FOR(i, maxSamples)
442         {
443             newSamples[i] = samples[perm[i]];
444             newLabels[i] = labels[perm[i]];
445         }
446         samples = newSamples;
447         labels = newLabels;
448         count = samples.size();
449         delete [] perm;
450     }
451     if(!excludeIndex.size()) return pair<vector<fvec>,ivec>(samples,labels);
452     vector<fvec> newSamples(count);
453     int newDim = dim - excludeIndex.size();
454     if(outputLabelColumn != -1) newDim--;
455     //qDebug() << "Indices to be excluded: " << excludeIndex.size() << "(newDim: " << newDim << ")";
456     FOR(i, excludeIndex.size())
457     {
458         //qDebug() << i << ":" << excludeIndex[i];
459         // if it's the output we can ignore it but we need to reincrement the number of dimensions
460         if(excludeIndex[i] == outputLabelColumn)
461         {
462             newDim++;
463             break;
464         }
465     }
466     vector<bool> bExclude(dim, false);
467     FOR(i, excludeIndex.size())
468     {
469         bExclude[excludeIndex[i]] = true;
470     }
471     FOR(i, samples.size())
472     {
473         newSamples[i].resize(newDim);
474         int nD = 0;
475         FOR(d, dim)
476         {
477             if(bExclude[d] || d == outputLabelColumn) continue;
478             if(outputLabelColumn == -1) newSamples[i][nD] = samples[i][d];
479             else if (d < outputLabelColumn) newSamples[i][nD] = samples[i][d];
480             else if(d > outputLabelColumn) newSamples[i][nD] = samples[i][d-1];
481             nD++;
482         }
483     }
484     qDebug() << "Imported samples: " << newSamples.size() << " labels: " << labels.size();
485     return pair<vector<fvec>,ivec>(newSamples,labels);
486 }
487
488
489 uint8_t CSVParser::getBOMsize(const char* fileName)
490 {
491     FILE *f = fopen(fileName,"rb");
492     unsigned char bom[16];
493     fread(bom,1,16,f);
494
495     if        (bom[0] == 0x00  && bom[1]  == 0x00 &&
496                bom[2] == 0xFE  && bom[3]  == 0xFF) {
497         cout << "Detected UTF-32 (BE) encoding" << endl;
498         return 4;
499     } else if (bom[0]  == 0xFF && bom[1]  == 0xFE &&
500                bom[2]  == 0x00 && bom[3]  == 0x00) {
501         cout << "Detected UTF-32 (LE) encoding" << endl;
502         return 4;
503     } else if (bom[0]  == 0xFE && bom[1]  == 0xFF) {
504         cout << "Detected UTF-16 (BE) encoding" << endl;
505         return 2;
506     } else if (bom[0]  == 0xFF && bom[1]  == 0xFE) {
507         cout << "Detected UTF-16 (LE) encoding" << endl;
508         return 2;
509     } else if (bom[0]  == 0xEF && bom[1]  == 0xBB &&
510                bom[2]  == 0xBF)                  {
511         cout << "Detected UTF-8 encoding" << endl;
512         return 3;
513     } else if (bom[0]  == 0x2B && bom[1]  == 0x2F &&
514                bom[2]  == 0x76 && bom[3]  == 0x38 &&
515
516                bom[4]  == 0x2B && bom[5]  == 0x2F &&
517                bom[6]  == 0x76 && bom[7]  == 0x39 &&
518
519                bom[8]  == 0x2B && bom[9]  == 0x2F &&
520                bom[10] == 0x76 && bom[11] == 0x2B &&
521
522                bom[12] == 0x2B && bom[13] == 0x2F &&
523                bom[14] == 0x76 && bom[15] == 0x2F) {
524         cout << "Detected UTF-7 encoding" << endl;
525         return 16;
526     } else if (bom[0]  == 0xF7 && bom[1]  == 0x64 &&
527                bom[2]  == 0x4C)                  {
528         cout << "Detected UTF-1 encoding" << endl;
529         return 3;
530     } else if (bom[0]  == 0xDD && bom[1]  == 0x73 &&
531                bom[2]  == 0x66 && bom[3]  == 0x73) {
532         cout << "Detected UTF-EBCDIC encoding" << endl;
533         return 4;
534     } else if (bom[0]  == 0x0E && bom[1]  == 0xFE &&
535                bom[2]  == 0xFF)                  {
536         cout << "Detected SCSU encoding" << endl;
537         return 3;
538     } else if (bom[0]  == 0xFB && bom[1]  == 0xEE &&
539                bom[2]  == 0x28)                  {
540         cout << "Detected BOCU-1 encoding" << endl;
541         return 3;
542     } else if (bom[0]  == 0x84 && bom[1]  == 0x31 &&
543                bom[2]  == 0x95 && bom[3]  == 0x33) {
544         cout << "Detected GB-18030 encoding" << endl;
545         return 4;
546     } else {
547         cout << "No BOM detected, possibly pure ASCII or UTF-8" << endl;
548         return 0;
549     }
550 }